# Tag Info

### 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 ...

### 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 ...
• 137k

### 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 ...
• 26.3k

### 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 ...
• 1,699
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 ...
• 78.3k

### 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 ...
• 1,909

### 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 ...
• 27.3k
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 ...
• 44.7k
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 ...
• 78.3k

### 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 ...
• 4,429

### 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 ...

### 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 ...
• 78.3k

### 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 ...
• 78.3k

### 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 ...
• 78.3k

### 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 (...
• 137k