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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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]}=...

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

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

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

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

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

#### Related Tags

proof-complexity × 21lo.logic × 13

computational-complexity × 11

proof-theory × 9

reference-request × 2

co.combinatorics × 2

formal-proof × 2

set-theory × 1

model-theory × 1

computability-theory × 1

forcing × 1

computer-science × 1

it.information-theory × 1

linear-programming × 1

foundations × 1

cryptography × 1

sums-of-squares × 1

decidability × 1

metamathematics × 1

bounded-arithmetic × 1

operations-research × 1