We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [proofs]

Used for questions about existing or possible proofs of a specific theorem or conjecture

Filter by
Sorted by
Tagged with
83
votes
10answers
14k views

What would it mean to disprove Church-Turing thesis?

Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why? Turing, Rosser etc ...
40
votes
4answers
3k views

Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

This is a question related to this one. Putting it again in a much simpler form after a lot of discussion there, that it felt like a totally different question. The classical proof of the ...
25
votes
4answers
2k views

Proofs, Barriers and P vs NP

It is well known that any proof resolving the P vs NP question must overcome relativization, natural proofs and algebrization barriers. The following diagram partitions the "proof space" into ...
55
votes
14answers
2k views

Where and how did computers help prove a theorem?

The purposes of this question is to collect examples from theoretical computer science where the systematic use of computers was helpful in building a conjecture that lead to a theorem, falsifying a ...
47
votes
8answers
4k views

Are there non-constructive algorithm existence proofs?

I remember I might have encountered references to problems that have been proven to be solvable with a particular complexity, but with no known algorithm to actually reach this complexity. I struggle ...
18
votes
4answers
3k views

Implications of unprovability of $P\neq NP$

I was reading "Is P Versus NP Formally Independent?" but I got puzzled. It is widely believed in complexity theory that $\mathsf{P} \neq \mathsf{NP}$. My question is about what if this is not ...
13
votes
1answer
923 views

Correctness proofs of classic Paxos and Fast Paxos

I am reading the "Fast Paxos" paper by Leslie Lamport and get stuck with the correctness proofs of both classic Paxos and Fast Paxos. For consistency, the value $v$ picked by the coordinator in phase ...
16
votes
2answers
729 views

Complexity of counting the number of edge covers of a graph

An edge cover is a subset of edges of a graph such that every vertex of the graph is adjacent to at least one edge of the cover. The following two papers say that counting edge covers is #P-complete: ...
1
vote
1answer
310 views

in SAT resolution proofs, are all DAGs possible? [closed]

these are some probably very hard but possibly significant and deep questions related to an unusual but intriguing possible "recursive" construction/formulation in SAT, with some important "structure" ...
1
vote
2answers
1k views

Is there an alternative proof of the TM Halting Problem other than the “standard” one? [closed]

I'm wondering if anyone is aware of a proof of the Halting Problem that is not just a permutation of the "standard" proof. Since there are so many formulations of this proof, rather than pick a ...
27
votes
5answers
854 views

Quantum proofs of classical theorems

I'm interested in examples of problems where a theorem which seemingly has nothing to do with quantum mechanics/information (e.g. states something about purely classical objects) can nevertheless be ...
22
votes
1answer
2k views

What's the status of Babai's Graph isomorphism result?

It's been over a year since his January 2017 retraction and correction. Is there news? If not is this normal for validation to take this long? I would expect it would get plenty of attention. Has ...
7
votes
2answers
395 views

Proof Strategies on P versus BPP

Typically to show $P=NP$, one has to show an NP complete problem has a polynomial time solution and to show $P\neq NP$, has to show an NP complete problem has superpolynomial lower bound. These are ...
4
votes
1answer
400 views

Proof that the graph optimization problem is NP-hard

I'm trying to prove that the following optimization problem is NP-hard: Given a graph $G=(V,E)$, non-negative vertex weight functions $w(v)$ and $s(v)$, and a non-negative edge weight function $t(u,v)...
11
votes
3answers
750 views

Where do I turn for help with research/publishing?

I have been developing a SAT algorithm for a while, and have reached a point where I'd like to share it. I don't know many people in computer science, and I'm not sure exactly where to turn. I'm ...
3
votes
3answers
899 views

What's wrong with this proof that NP=Co-NP implies NP=PSPACE

Below is a short informal proof that NP=co-NP implies NP=PSPACE. What's wrong with the proof? Assuming NP=co-NP, an instance F of TQBF can be solved by a polynomial NDTM this way: Non-...