pith. sign in

arxiv: 2607.01671 · v1 · pith:IGRUFF7Gnew · submitted 2026-07-02 · 💻 cs.CC · cs.DS· cs.IT· cs.LO· math.IT

Self-Referential K-SAT and the Finite Analogue of G\"odel's Incompleteness Theorem

Wen Fang , Xianxian Li , Jun Liu , Jie Luo , Yongxin Tong , Ke Xu This is my paper

Pith reviewed 2026-07-03 02:23 UTC · model grok-4.3

classification 💻 cs.CC cs.DScs.ITcs.LOmath.IT
keywords self-referential K-SATfinite Gödel incompletenessResolution proof complexityStrong Exponential Time Hypothesisinformational blind spotPoisson distributionproof explosionlocal indistinguishability
0
0 comments X

The pith

Log-width K-SAT admits self-referential clause substitutions that produce locally indistinguishable SAT/UNSAT pairs and force exponential Resolution proofs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper builds a finite combinatorial analogue of Gödel's incompleteness inside Boolean K-SAT. In the logarithmic-width ensemble, satisfying assignments follow a Poisson distribution, allowing unsatisfiable formulas and uniquely satisfiable formulas to coexist. A single-clause substitution conditioned on the unique solution then yields pairs that agree under every local check yet differ in satisfiability. Any deductive process limited to a sublinear window therefore encounters an informational blind spot that raises the descriptive complexity of the formula. This forces Resolution refutations of the UNSAT member to use wide clauses and produces proof sizes that grow exponentially toward the full 2^N bound.

Core claim

Executing a single-clause substitution conditioned on the unique solution produces structurally irreducible SAT/UNSAT pairs indistinguishable via local evaluation. Deductive pipelines restricted to a sublinear window suffer an informational blind spot that forces a descriptive lower bound K(A) >= Omega(N^{1-delta}). This deficit compels any Resolution refutation of the UNSAT instance to use wide clauses of width Omega(N^{1-delta}), which triggers an exponential proof-tree explosion S(phi) >= exp(Omega(N^{1-2delta})). As delta tends to zero, the bound converges to the worst-case 2^N threshold.

What carries the argument

Single-clause substitution conditioned on the unique solution, which creates structurally irreducible yet locally indistinguishable SAT/UNSAT pairs.

If this is right

  • Any sublinear-window deduction encounters an informational blind spot requiring superlinear descriptive complexity.
  • Resolution refutations must employ clauses of width at least Omega(N^{1-delta}) to achieve refutation.
  • Proof size grows at least exponentially as exp(Omega(N^{1-2delta})), approaching 2^N.
  • Self-referential hardness precludes quantum shortcuts that rely on local analysis.
  • Machine learning on lossy local compression encounters a scaling bottleneck from this hardness.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The substitution technique may extend to other NP-complete problems such as graph coloring to derive similar proof lower bounds.
  • Empirical checks on moderate-sized instances could test whether the constructed pairs resist standard local SAT solvers.
  • The link to algorithmic information theory suggests direct measurement of Kolmogorov complexity on generated examples.

Load-bearing premise

Satisfying assignments in the logarithmic-width K-SAT ensemble converge to a Poisson distribution, allowing unsatisfiable and uniquely satisfiable formulas to coexist.

What would settle it

A local evaluation procedure that distinguishes the substituted SAT instance from its UNSAT counterpart without global structure would refute the informational blind spot.

read the original abstract

Self-reference and solution independence are core properties underlying intractability. This paper establishes a finite combinatorial analogue of G\"odel's incompleteness theorems within Boolean $K$-SAT. While standard random $K$-SAT has assignment correlations that disrupt solution independence, we resolve this via a logarithmic-width ensemble ($K = O(\log N)$). Here, satisfying assignments converge to a Poisson distribution, letting unsatisfiable and uniquely satisfiable formulas coexist. By executing a single-clause substitution conditioned on the unique solution, we construct structurally irreducible SAT/UNSAT pairs that are indistinguishable via local evaluation. Using algorithmic information theory and Shannon channels, we prove that deductive pipelines restricted to a sublinear window suffer from an informational blind spot, forcing a descriptive lower bound of $K(\mathcal{A}) \geq \Omega(N^{1-\delta})$. This deficit forces any Resolution refutation of the UNSAT instance to utilize wide clauses ($w(\pi) \geq \Omega(N^{1-\delta})$), triggering an exponential proof-tree explosion ($S(\phi) \geq \exp(\Omega(N^{1-2\delta}))$). As $\delta \rightarrow 0^+$, this bound converges to the worst-case $2^N$ threshold, reframing the Strong Exponential Time Hypothesis (SETH) as a direct projection of G\"odel incompleteness onto finite computation. We diagnose the decades-long stagnation in complexity theory. Transitioning from Turing's class separation to a G\"odelian paradigm of instance indistinguishability, we introduce a multi-dimensional comparative framework that contrasts these two historical lineages across distinct perspectives. The self-referential hardness exhibits physical invariance: it precludes quantum shortcuts due to the necessity of global semantic analysis and delineates a scaling bottleneck for machine learning architectures operating on lossy, local compression.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper claims to establish a finite analogue of Gödel's incompleteness theorem in Boolean K-SAT. Using a logarithmic-width ensemble (K = O(log N)) in which satisfying assignments are asserted to converge to a Poisson distribution, it constructs structurally irreducible SAT/UNSAT pairs via single-clause substitution that remain locally indistinguishable. Algorithmic information theory is then invoked to derive an informational blind spot for sublinear deductive pipelines, yielding Kolmogorov complexity lower bound K(A) ≥ Ω(N^{1-δ}), Resolution width lower bound w(π) ≥ Ω(N^{1-δ}), and proof-size lower bound S(φ) ≥ exp(Ω(N^{1-2δ})). As δ → 0^+, this is said to recover the 2^N threshold and reframe SETH as a direct projection of incompleteness; the paper also contrasts Turing-style and Gödelian paradigms and discusses implications for quantum computing and machine learning.

Significance. If the central derivations were supplied and the Poisson-convergence step rigorously justified, the work would supply a novel self-referential explanation for exponential proof complexity and SETH, together with a comparative framework contrasting historical approaches to intractability. The explicit construction of indistinguishable SAT/UNSAT pairs and the attempt to derive width lower bounds from an information-theoretic deficit would constitute a concrete technical contribution, even if the ultimate reframing of SETH remains debatable.

major comments (3)
  1. [Abstract] Abstract (paragraph beginning 'While standard random K-SAT...'): The claim that 'satisfying assignments converge to a Poisson distribution' for the K = O(log N) ensemble is asserted without derivation, threshold calculation, error analysis, or citation. Standard Poisson approximations in the random K-SAT literature apply to fixed K; when K grows with N the local statistics may retain correlations or the probability of unique solutions may vanish. This step is load-bearing for the subsequent claim that unsatisfiable and uniquely satisfiable formulas coexist at the same density and therefore for the single-clause substitution construction of locally indistinguishable pairs.
  2. [Abstract] Abstract (paragraph beginning 'Using algorithmic information theory...'): The passage from the informational blind spot K(A) ≥ Ω(N^{1-δ}) to the Resolution width lower bound w(π) ≥ Ω(N^{1-δ}) and then to the proof-size bound S(φ) ≥ exp(Ω(N^{1-2δ})) is stated without intermediate lemmas or explicit steps showing how a Kolmogorov-complexity deficit on sublinear windows forces wide clauses in a Resolution refutation. The translation from descriptive complexity to proof width is therefore not verifiable from the given text.
  3. [Abstract] Abstract (final paragraph on SETH): The assertion that the derived bound 'converges to the worst-case 2^N threshold' and thereby reframes SETH as 'a direct projection of Gödel incompleteness' rests on the indistinguishability property produced by the paper's own ensemble and substitution construction. No independent argument is supplied showing that the same lower bound holds for arbitrary formulas outside this specially engineered family.
minor comments (2)
  1. [Abstract] The multi-dimensional comparative framework contrasting Turing and Gödelian lineages is announced but not developed with concrete dimensions or tables; a brief tabular summary would improve readability.
  2. Notation: the symbols K(A), w(π), and S(φ) are introduced without an explicit definitions section or reference to standard definitions in the literature on Kolmogorov complexity and Resolution complexity.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their thorough review and valuable feedback. We address each of the major comments point by point below. Where the manuscript lacks sufficient detail or clarity in the abstract, we commit to revisions that strengthen the presentation.

read point-by-point responses

  1. Referee: [Abstract] Abstract (paragraph beginning 'While standard random K-SAT...'): The claim that 'satisfying assignments converge to a Poisson distribution' for the K = O(log N) ensemble is asserted without derivation, threshold calculation, error analysis, or citation. Standard Poisson approximations in the random K-SAT literature apply to fixed K; when K grows with N the local statistics may retain correlations or the probability of unique solutions may vanish. This step is load-bearing for the subsequent claim that unsatisfiable and uniquely satisfiable formulas coexist at the same density and therefore for the single-clause substitution construction of locally indistinguishable pairs.

    Authors: We agree that the abstract presents this claim without the supporting derivation. We will add a dedicated lemma in the revised manuscript deriving the Poisson convergence for the K = O(log N) ensemble, including threshold calculation using adapted local lemma arguments, error analysis via concentration bounds, and citations to related work on growing clause widths. This addresses the load-bearing nature of the step. revision: yes

  2. Referee: [Abstract] Abstract (paragraph beginning 'Using algorithmic information theory...'): The passage from the informational blind spot K(A) ≥ Ω(N^{1-δ}) to the Resolution width lower bound w(π) ≥ Ω(N^{1-δ}) and then to the proof-size bound S(φ) ≥ exp(Ω(N^{1-2δ})) is stated without intermediate lemmas or explicit steps showing how a Kolmogorov-complexity deficit on sublinear windows forces wide clauses in a Resolution refutation. The translation from descriptive complexity to proof width is therefore not verifiable from the given text.

    Authors: We agree that the abstract does not include the intermediate steps. We will insert explicit lemmas in the revised version detailing the translation from the Kolmogorov complexity deficit on sublinear windows to the Resolution width lower bound, including the mechanism by which the informational blind spot forces wide clauses, followed by the exponential proof-size bound. revision: yes

  3. Referee: [Abstract] Abstract (final paragraph on SETH): The assertion that the derived bound 'converges to the worst-case 2^N threshold' and thereby reframes SETH as 'a direct projection of Gödel incompleteness' rests on the indistinguishability property produced by the paper's own ensemble and substitution construction. No independent argument is supplied showing that the same lower bound holds for arbitrary formulas outside this specially engineered family.

    Authors: We agree that the lower bounds and indistinguishability are shown for the specific ensemble and substitution construction. We will revise the abstract language to clarify that the reframing of SETH is an interpretive consequence based on this family rather than an independent general proof for arbitrary formulas outside the construction. revision: yes

Circularity Check

1 steps flagged

Indistinguishability of constructed SAT/UNSAT pairs forces informational blind spot by design

specific steps
  1. self definitional [Abstract]
    "By executing a single-clause substitution conditioned on the unique solution, we construct structurally irreducible SAT/UNSAT pairs that are indistinguishable via local evaluation. Using algorithmic information theory and Shannon channels, we prove that deductive pipelines restricted to a sublinear window suffer from an informational blind spot, forcing a descriptive lower bound of K(A) ≥ Ω(N^{1-δ}). This deficit forces any Resolution refutation of the UNSAT instance to utilize wide clauses (w(π) ≥ Ω(N^{1-δ})), triggering an exponential proof-tree explosion (S(φ) ≥ exp(Ω(N^{1-2δ})))."

    The pairs are defined via the substitution construction to be locally indistinguishable; the informational blind spot, descriptive lower bound, and Resolution width lower bound are then proven for exactly those pairs using the indistinguishability property that was built in. The exponential bound and SETH reframing therefore follow by construction from the chosen ensemble and substitution rather than from an independent property of random K-SAT.

full rationale

The paper's core derivation begins with an asserted Poisson convergence in the K=O(log N) ensemble (no derivation or citation supplied) to enable coexistence of unsatisfiable and uniquely satisfiable formulas, followed by a single-clause substitution that explicitly constructs pairs declared to be locally indistinguishable. The subsequent informational blind spot, K(A) lower bound, Resolution width lower bound, and exponential proof-size explosion are then derived for these pairs. Because the indistinguishability property is introduced by the construction itself, the blind-spot and hardness claims reduce to consequences of the definition rather than independent results, producing partial circularity. The reframing of SETH as a Gödel projection inherits this dependence. No self-citations or fitted parameters are involved, keeping the score at 6 rather than higher.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 1 invented entities

The central claim depends on the non-standard choice of logarithmic ensemble and the asserted Poisson convergence, neither of which is justified from prior literature in the abstract; the informational blind spot is introduced ad hoc to derive the descriptive lower bound.

free parameters (2)
  • K (clause width) = O(log N)
    Set to O(log N) to achieve the Poisson distribution of satisfying assignments
  • delta
    Controls the sublinear window and appears in the exponents of the lower bounds on clause width and proof size
axioms (2)
  • domain assumption Satisfying assignments converge to a Poisson distribution in the log-width ensemble
    Invoked to permit coexistence of unsatisfiable and uniquely satisfiable formulas
  • ad hoc to paper Deductive pipelines restricted to a sublinear window suffer from an informational blind spot
    Used to obtain the lower bound K(A) ≥ Ω(N^{1-δ})
invented entities (1)
  • structurally irreducible SAT/UNSAT pairs no independent evidence
    purpose: To serve as locally indistinguishable instances that force wide-clause proofs
    Created by single-clause substitution conditioned on the unique solution

pith-pipeline@v0.9.1-grok · 5888 in / 1867 out tokens · 42808 ms · 2026-07-03T02:23:14.499838+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

60 extracted references · 4 canonical work pages · 3 internal anchors

  1. [1]

    Aaronson and A

    S. Aaronson and A. Wigderson. Algebrization: A new barrier in complexity theory.ACM Transactions on Computation Theory, 1(1):1–54, 2009

    2009

  2. [2]

    Aaronson

    S. Aaronson. P ? = NP.Open problems in mathematics, pp. 1-122. Springer, Cham, 2016

    2016

  3. [3]

    Arora, B

    S. Arora, B. Barak.Computational Complexity: A Modern Approach. Cambridge: Cam- bridge University Press, 2009

    2009

  4. [4]

    Arratia, L

    R. Arratia, L. Goldstein, and L. Gordon. Two moments suffice for Poisson approximations: the Chen–Stein method.Annals of Probability, 17(1):9-25, 1989

    1989

  5. [5]

    Baker, J

    T. Baker, J. Gill, and R. Solovay (1975). Relativizations of the P =? NP question.SIAM Journal on Computing, 4(4):431–442, 1975

    1975

  6. [6]

    Ben-Sasson and A

    E. Ben-Sasson and A. Wigderson. Short proofs are narrow—resolution made simple. Journal of the ACM, 48(2):149–169, 2001

    2001

  7. [7]

    Budiansky.Journey to the edge of reason: The life of Kurt G¨ odel

    S. Budiansky.Journey to the edge of reason: The life of Kurt G¨ odel. Oxford University Press, 2021

    2021

  8. [8]

    B¨ urgisser, C

    P. B¨ urgisser, C. Ikenmeyer, and G. Panova. No occurrence obstructions in geometric complexity theory.Journal of the American Mathematical Society, 32(1):163-193, 2019

    2019

  9. [9]

    Calabro, R

    C. Calabro, R. Impagliazzo, and R. Paturi. The complexity of satisfiability of small depth circuits.International Workshop on Parameterized and Exact Computation, pp. 75-85, 2009

    2009

  10. [10]

    G.J. Chaitin. On the difficulty of computations.IEEE Transactions on Information Theory, 116 (2):155-159, 1970. 30

    1970

  11. [11]

    G.J. Chaitin. Information-theoretic limitations of formal systems.Journal of the ACM, 21(3):403-424, 1974

    1974

  12. [12]

    J. Chen, X. Huang, I.A. Kanj, and G. Xia. Strong computational lower bounds via parameterized complexity.Journal of Computer and System Sciences, 72(8):1346–1367, 2006

    2006

  13. [13]

    A. Church. An unsolvable problem of elementary number theory.American Journal of Mathematics, 58(2):345–363, 1936

    1936

  14. [14]

    S.A. Cook. The complexity of theorem-proving procedures.Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151-158, 1971

    1971

  15. [15]

    Cook and R.A

    S.A. Cook and R.A. Reckhow. The relative efficiency of propositional proof systems.The Journal of Symbolic Logic, 44(1):36-50, 1979

    1979

  16. [16]

    Cover and J.A

    T.M. Cover and J.A. Thomas.Elements of Information Theory (2nd ed.). Wiley- Interscience, 2006

    2006

  17. [17]

    Csisz´ ar, I

    I. Csisz´ ar, I. and Z. Talata. Context tree estimation for not necessarily finite memory processes, via BIC and MDL.IEEE Transactions on Information theory, 52(3):1007-1016, 2006

    2006

  18. [18]

    Cygan, H

    M. Cygan, H. Dell, D. Lokshtanov, D. Marx, J. Nederlof, Y. Okamoto., R. Paturi, S. Saurabh, and M. Wahlstr¨ om. On problems as hard as CNF-SAT.ACM Transactions on Algorithms, 12(3):1-24, 2016

    2016

  19. [19]

    Dijkstra

    E.W. Dijkstra. A note on two problems in connexion with graphs.Numerische Mathe- matik, 1(1):269–271, 1959

    1959

  20. [20]

    J. Ding, A. Sly, and N. Sun. Proof of the satisfiability conjecture for large k.Annals of Mathematics, 196(1):1-388, 2022

    2022

  21. [21]

    Downey and M.R

    R.G. Downey and M.R. Fellows.Parameterized Complexity. Springer, 1999

    1999

  22. [22]

    Efremenko, Klim A

    K. Efremenko, Klim A. Garg, R. Oliveira, A. Wigderson. Barriers for rank methods in arithmetic complexity.9th Innovations in Theoretical Computer Science Conference, 2018

    2018

  23. [23]

    Fortnow and S

    L. Fortnow and S. Homer. A short history of computational complexity.Bulletin of EATCS, 80:95-133, 2003

    2003

  24. [24]

    Franco and M

    J. Franco and M. Paull. Probabilistic analysis of the Davis–Putnam procedure for solving the satisfiability problem.Discrete Applied Mathematics, 5(1):77–87, 1983

    1983

  25. [25]

    Friedman

    H.M. Friedman. Finite functions and the necessary use of large cardinals.Annals of Mathematics, 148(3):803-893, 1998

    1998

  26. [26]

    Frieze and N.C

    A. Frieze and N.C. Wormald. Random k-SAT: A tight threshold for moderately growing k.Combinatorica25(3):297-305, 2005. 31

    2005

  27. [27]

    A. P. Godbole and S. Janson. Random covering designs.Journal of Combinatorial Theory, Series A, 75(1):85–98, 1996

    1996

  28. [28]

    G¨ odel.¨Uber formal unentscheidbare S¨ atze der Principia Mathematica und verwandter Systeme I.Monatshefte f¨ ur Mathematik und Physik, 38:173–198, 1931

    K. G¨ odel.¨Uber formal unentscheidbare S¨ atze der Principia Mathematica und verwandter Systeme I.Monatshefte f¨ ur Mathematik und Physik, 38:173–198, 1931

    1931

  29. [29]

    Hartmanis and R.E

    J. Hartmanis and R.E. Stearns. On the computational complexity of algorithms.Trans- actions of the American Mathematical Society, 117:285–306, 1965

    1965

  30. [30]

    Hartmanis

    J. Hartmanis. On computational complexity and the nature of computer science.ACM Computing Surveys, 27(1):7-16, 1995

    1995

  31. [31]

    D. Hilbert. Probleme der Grundlegung der Mathematik.Mathematische Annalen, 102(1):1-9, 1930

    1930

  32. [32]

    Kraj´ ıˇ cek.Bounded arithmetic, propositional logic and complexity theory(Vol

    J. Kraj´ ıˇ cek.Bounded arithmetic, propositional logic and complexity theory(Vol. 60). Cambridge University Press, 1995

    1995

  33. [33]

    Lau (translated).Tao Te Ching

    D.C. Lau (translated).Tao Te Ching. London: Penguin Books, 1963

    1963

  34. [34]

    Li and Y

    A. Li and Y. Pan. Structural information and dynamical complexity of networks.IEEE Transactions on Information Theory, 62(6):3290-3339, 2016

    2016

  35. [35]

    Li .Science of artificial intelligence: Mathematical principles of intelligence(in Chinese)

    A. Li .Science of artificial intelligence: Mathematical principles of intelligence(in Chinese). Science Press, 2024

    2024

  36. [36]

    J. Li, S. Hu, X. Li, and M. Yin. Constructing self-referential instances for the clique problem. arXiv:2601.19393, 2026

    work page arXiv 2026

  37. [37]

    Li and P

    M. Li and P. Vit´ anyi.An introduction to Kolmogorov complexity and its applications. Springer, 2008

    2008

  38. [38]

    Li.Mathematical logic: Foundations for information science

    W. Li.Mathematical logic: Foundations for information science. Birkh¨ auser Basel, 2010

    2010

  39. [39]

    J. Liu, Z. Gao, and K. Xu. A note on random k-SAT for moderately growing k.The Electronic Journal of Combinatorics19(1), P24, 2012

    2012

  40. [40]

    Mulmuley

    K. Mulmuley. On P vs. NP and geometric complexity theory: Dedicated to Sri Ramakr- ishn.Journal of the ACM, 58(2) :1–26, 2011

    2011

  41. [41]

    Paris, L

    J. Paris, L. Harrington. A mathematical incompleteness in Peano arithmetic.Studies in Logic and the Foundations of Mathematics, 90:1133-1142, 1977

    1977

  42. [42]

    Paturi, P

    R. Paturi, P. Pudl´ ak, M.E. Saks, and F. Zane. An improved exponential-time algorithm fork-SAT.Journal of the ACM, 52(3):337-364, 2005

    2005

  43. [43]

    X. Peng, J. Wu, Y. Hou, Z. Qiao, J. Liu, S. Li, J. Zhao, W. Wu, X. Liu, Y. Tong, L. Dong, and K. Xu. Can machines really see objects in images? A study based on syntactic distance and visual self-referential instances. arXiv:2606.29416, 2026. 32

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  44. [44]

    Pinsker.Information and information stability of random variables and processes

    M.S. Pinsker.Information and information stability of random variables and processes. Translated and edited by Amiel Feinstein. Holden-Day, Inc., San Francisco, 1964

    1964

  45. [45]

    Plotkin.A structural approach to operational semantics

    G.D. Plotkin.A structural approach to operational semantics. Aarhus university, 1981

    1981

  46. [46]

    Razborov and S

    A.A. Razborov and S. Rudich. Natural proofs.Journal of Computer and System Sciences, 55(1):24–35, 1997

    1997

  47. [47]

    P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124-134, 1994

    1994

  48. [48]

    C.E. Shannon. A mathematical theory of communication.The Bell System Technical Journal, 27(3):379-423, 1948

    1948

  49. [49]

    A. Tarsky. The concept of truth in formalized languages.Logic, semantics, metamathe- matics, pp. 152-278, 1956

    1956

  50. [50]

    Tsybakov.Introduction to Nonparametric Estimation

    A.B. Tsybakov.Introduction to Nonparametric Estimation. Springer, 2009

    2009

  51. [51]

    A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42:230–265, 1936

    1936

  52. [52]

    Wigderson.Mathematics and computation: A theory revolutionizing technology and science

    A. Wigderson.Mathematics and computation: A theory revolutionizing technology and science. Princeton University Press, 2019

    2019

  53. [53]

    Williams

    V.V. Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In10th International Symposium on Parameterized and Exact Computation(IPEC), pp. 17-29, 2015

    2015

  54. [54]

    Wittgenstein.Lectures on the foundations of mathematics, Cambridge, 1939: From the Notes of R.G

    L. Wittgenstein.Lectures on the foundations of mathematics, Cambridge, 1939: From the Notes of R.G. Bosanquet, N. Malcolm, R. Rhees, and Y. Smythies. Harvester Press, 1976

    1939

  55. [55]

    Wittgenstein,Tractatus Logico-Philosophicus, translated by D

    L. Wittgenstein,Tractatus Logico-Philosophicus, translated by D. F. Pears and B. F. McGuinness, Routledge, 1961

    1961

  56. [56]

    Xu and W

    K. Xu and W. Li. Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research, 12(1):93-103, 2000

    2000

  57. [57]

    Xu and G

    K. Xu and G. Zhou. SAT requires exhaustive search.Frontiers of Computer Science, 19:1912405, 2025

    2025

  58. [58]

    Xu and G

    K. Xu and G. Zhou. Self-reference as key to proving extreme hardness—Reply to the comment by Allender and Williams, 2025. Available:https://rb-bench.github.io/

    2025

  59. [59]

    G. Zhou. Self-referential instances of the dominating set problem are irreducible. arXiv:2602.10559, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  60. [60]

    G. Zhou, B. Wang, J. Wang, and K. Xu. Solution independence and self-referential instances. arXiv:2605.02174, 2026. 33

    work page internal anchor Pith review Pith/arXiv arXiv 2026