# Questions tagged [proofs]

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

71 questions
Filter by
Sorted by
Tagged with
875 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 ...
2k views

### Why is Feige-Fiat-Shamir not Zero Knowledge without sign bits?

In chapter 10 of HAC (10.4.2), we see the well-known Feige-Fiat-Shamir identification protocol based on a zero-knowledge proof using the (presumed) difficulty of extracting square roots modulo a ...
411 views

### Can we infer the next player in chess from the current board configuration?

Presume that a program memory only includes the current state for instance of a chess board. Does it need the variable which player, black or white, has the next turn to move or is it redundant ...
5k views

### Proof of the pumping lemma for context-free languages using pushdown automata

The pumping lemma for regular languages can be proved by considering a finite state automaton which recognizes the language studied, picking a string with a length greater than its number of states, ...
912 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-...
205 views

### More elementary proof of coloring theorem for d x d^2 rectangles

The following is known: For all $c$, for all $c$-colorings of $N\times N$ there exists a $d \times d^2$ rectangle ($d \ge 2$) such that all four corners are the same color. The proof uses the Poly-...
835 views

### Proofs obtained only through spectral graph theory

I have an increasing interest in spectral graph theory, which I find fascinating, and I've started collecting a few documents that I have yet to read more thoroughly than what I so far have. However, ...
234 views

### No Fair Merge via Nondeterminstic Data Flow Streams

While reading Wikipedia, I ran across a proof given on Unbounded Nondeterminism that I do not understand. The proof is given as, An example of the role of fair or unbounded nondeterminism in the ...
309 views

### Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$

I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$. I'm now searching for an intuitive, or geometric, or visual proof of ...
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 ...
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 ...
935 views

### An Interactive Proof of God's Number?

I've been learning about interactive proofs lately and I've been wondering if the whole thing was nothing more than a theoretical curiosity, or if it had any practical applications. I thought I'd ...
1k views

### Proofs that expose a deeper structure

The standard proof of the Chernoff bound (from the Randomized Algorithms textbook) uses the Markov inequality and moment generating functions, with a bit of a Taylor expansion thrown in. Nothing too ...
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 ...
4k views

### Simple proof of Ω(n lg n) worst-case bound for uniqueness/distinctness?

There are several proofs for the loglinear lower bound for the element uniqueness/distinctness problem (based on algebraic computation trees or adversarial arguments), but I'm looking for one that's ...
3k views

On MathOverflow, Timothy Gowers asked a question titled "Demonstrating that rigour is important". Most of the discussion there was about cases showing the importance of proof, which people on ...
4k views

### What techniques are used for proving algorithms optimal? [duplicate]

Possible Duplicate: Problems that can be used to show polynomial time hardness results Given a polynomial time algorithm, what techniques are known for proving that an algorithm is optimal? E.g.,...
757 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 ...
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 ...