16 votes

Connections between Complexity Theory & Set Theory

See Diagonalizations over polynomial time computable sets in which two types of genericity introduced with which it examines complexity properties provable by simple diagonalizations over $P$. See ...
Mohammad Golshani's user avatar
15 votes

When do you get to the point of writing proofs that need to be so complicated that verifying the details becomes a great burden on others?

If your goal is to make arguments that need much more justification than you've given them, you're off to a great start with your argument that, because Fukaya wrote a paper that skipped a lot of ...
Will Sawin's user avatar
  • 137k
15 votes

Computational complexity theoretic incompleteness: is that a thing?

Consider the sentence $P(n)$ which says "This sentence has no proof shorter than $n$ characters." This sentence is true, and even has a proof - enumerate all strings of length $n$ and check ...
Sam Nead's user avatar
  • 26.3k
14 votes

Is there good reference for proof complexity?

These are three books that I know: Logical Foundations of Proof Complexity Bounded Arithmetic, Propositional Logic and Complexity Theory Logical Foundations of Mathematics and Computational ...
Erfan Khaniki's user avatar
10 votes
Accepted

Computational complexity theoretic incompleteness: is that a thing?

Yes, this sort of thing has been considered before, for example by Harvey Friedman and Pavel Pudlák. Here is a representative result. If we let $\mathsf{Con}(\mathsf{PA},n)$ denote the statement that ...
Timothy Chow's user avatar
  • 78.3k
9 votes

MIP*=RE theorem and its impact on logic and proof theory

MIP* = RE does not imply that a model of quantum computation can solve undecidable problems, as you correctly intuit. Instead, it establishes the existence of (a type of) interactive proofs for the ...
Henry Yuen's user avatar
  • 1,909
8 votes

Can infinity shorten proofs a lot?

A good example is a solution to Hilbert's third problem: it is not possible to cut the unit cube into finitely many polyhedral pieces and reassemble then as the regular tetrahedron of unit volume. The ...
Piotr Hajlasz's user avatar
7 votes
Accepted

Bounded Arithmetic vs Complexity Theory

If $T_1$ and $T_2$ are theories corresponding to complexity classes $C_1$ and $C_2$ (resp.), then separation of $C_1$ from $C_2$ from $C_2$ implies separation of $T_1$ from $T_2$, but not necessarily ...
Emil Jeřábek's user avatar
7 votes
Accepted

MIP*=RE theorem and its impact on logic and proof theory

You wrote: maybe there is some undecidable problem on which now we can shed some more light … Depending on what you mean by "shed some more light," the answer is yes; the original paper ...
Timothy Chow's user avatar
  • 78.3k
7 votes

Computational complexity theoretic incompleteness: is that a thing?

This might be more of an analogy, but major complexity conjectures like P=NP could be considered related. Background: a common "complete" problem for a specified time limit is: given a ...
usul's user avatar
  • 4,429
7 votes

Computational complexity theoretic incompleteness: is that a thing?

These self-referential decision problems are already part of the subject of computational complexity. There are analogues of the halting problem, for example, for many of the various classes in the ...
Joel David Hamkins's user avatar
6 votes

Connections between Complexity Theory & Set Theory

As far as I'm aware, large cardinals have not found any application in complexity theory. The main concepts from set theory that have found some application in complexity theory are forcing and ...
Timothy Chow's user avatar
  • 78.3k
5 votes

Bounded Arithmetic vs Complexity Theory

The arithmetic theories you're talking about typically have the property that the provably total functions are precisely the functions in some familiar complexity class. So suppose that the provably ...
Timothy Chow's user avatar
  • 78.3k
4 votes

Zero-knowledge proof for $P \ne NP$?

First of all, it does not really make sense to talk about zero-knowledge proofs for a single statement such as $P\ne NP$. You really should be asking about whether there is a zero-knowledge proof for ...
Timothy Chow's user avatar
  • 78.3k
4 votes

Zero-knowledge proof for $P \ne NP$?

If your friend is willing to part with an upper bound $B$ on the length of the proof in some formal system, then you can Take a computer program which verifies proofs in that formal system, which (...
Will Sawin's user avatar
  • 137k
3 votes

Oracle queries asked in parallel

By a standard argument that also applies in this case, polynomially parallel many witness queries give the same power as $O(\log n)$ many sequential witness queries: $$\mathrm{FP^{\|\Sigma^P_1[wit]}=...
Emil Jeřábek's user avatar
2 votes
Accepted

Does extended Frege p-simulate circuit Frege with substitutions?

The answer is yes. I’d say this is essentially folklore, but if you want a published reference, see Lemma 2.6 in my paper [1]. The lemma is stated more generally for proof systems for transitive modal ...
Emil Jeřábek's user avatar
1 vote

Hardness of a Hybrid problem combining knapsack and scheduling

It is NP-hard. Below is a reduction from the subset sum problem. The subset sum problem with positive inputs asks for a list of positive integers $a_1,\dots,a_n$ whether a subset of them has the sum $...
icecuber's user avatar
  • 330
1 vote

Hardness of a Hybrid problem combining knapsack and scheduling

I think your problem is exactly the scheduling problem: $$Q2|\bar {d_i} = d|\sum U_i$$ which is a particular case of the more general scheduling problem: $$Q2||\sum u_i U_i$$ which according to the ...
Stef's user avatar
  • 111
1 vote

Zero-knowledge proof for $P \ne NP$?

This is just a long comment, but it probably depends on the actual structure of the proof. Imagine some Ramsey-theoretical question, and you have proved that all graphs with property P are Hamiltonian....
Per Alexandersson's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible