Questions tagged [proofs]
Used for questions about existing or possible proofs of a specific theorem or conjecture
19
questions
94
votes
9
answers
19k
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 ...
user200
43
votes
4
answers
4k
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 ...
- 1,762
57
votes
18
answers
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 ...
25
votes
4
answers
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 ...
- 10.6k
51
votes
8
answers
5k
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 ...
- 8,751
29
votes
4
answers
5k
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 ...
- 407
16
votes
2
answers
989
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: ...
- 8,234
13
votes
1
answer
1k
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 ...
- 2,329
1
vote
2
answers
2k
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 ...
- 217
1
vote
1
answer
329
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" ...
- 10.9k
29
votes
1
answer
4k
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 ...
- 434
27
votes
5
answers
933
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 ...
- 2,796
15
votes
1
answer
1k
views
Examples of algorithms and proofs that seem correct, but aren't
In my intro to programming course, we're learning about the Initialization-Maintenance-Termination method of proving an algorithm does what we expect it to. But we've only had to prove that an ...
- 153
12
votes
4
answers
4k
views
Proof of Levenshtein distance
In the article Levenshtein distance Wikipedia says about the proof of invariant that:
This proof fails to validate that the number placed in d[i,j] is in
fact minimal; this is more difficult to ...
- 371
11
votes
3
answers
799
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 ...
- 2,080
7
votes
2
answers
727
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 ...
- 12.6k
4
votes
1
answer
481
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)...
- 239
3
votes
3
answers
1k
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-...
- 147
-4
votes
1
answer
1k
views
Alternative Turing Machine Proofs
I am asking this question again. I am aware of, and have read the other similar "alternative proof TM" questions, but unfortunately, they do help me.
I am looking for a TM Halting Problem proof that ...
- 217