# 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
543 views

### Examples of the value of proofs for algorithms

In teaching Intro. Algorithms to undergrads, one of the most difficult tasks is to motivate why they need to know how to prove things about algorithms. (For many students, at least in many US ...
180 views

### Document references describing weaknesses for cutting planes and algebraic proof system?

Here, Fortnow says (section 4.3): Since then complexity theorists have shown similar weaknesses in a number of other proof systems including cutting planes, algebraic proof systems based on ...
108 views

### Uniqueness of the distribution maximizing the channel capacity

Setting: We look at a discrete memoryless channel which takes an input probability distribution acting over symbols in $\mathcal{X}$ to an output probability distribution over symbols in $\mathcal{Y}$....
63 views

### Formally prove that the loops of this sorting algorithm will terminate [closed]

Given is the sorting algorithm Bubblesort ...
279 views

### EXPSPACE proof and its implications

I'm dealing with the min-max regret 0-1 Integer Linear Programming problem (MMR-ILP, for short), which is formulated as below. \begin{equation} \label{eq:nip_obj} \min_{x \in \Phi} \sum_{i = 1}^n ...
470 views

### Possible to do Complexity theory with only counting and Pigeonhole

Most of the proofs in the book Computational complexity by Barak and Arora seem to be Pigeonhole in disguise. What are some places in Complexity theory where counting and Pigeonhole was insufficient ...
243 views

### How would proof of the Lindelöf hypothesis improve our understanding of computational complexity classes?

A recent press release from the Viterbi School of Engineering at USC discussed the proof of the Lindelöf hypothesis by Athanassios Fokas, a visiting professor from the Department of Applied ...
111 views

### Proof of Sipser-Lautmann Theorem

I have written the following answer as an attempt to prove a variation of Sispser-Lautmann theorem, but it was rejected without any comments. I would appreciate if anyone can find the flaws in this ...
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 ...
3k 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 ...
371 views

### Formally proving no algorithm exists [closed]

Are there standard techniques to show that no algorithms exist for given complexity constraints? For example, consider the following problem. The input is a list of items with exactly one duplicate, ...
205 views

### Graph optimization problem with multiple objectives/constraints

Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We can divide vertices in ...
406 views

172 views

### Prove algorithm non-existence: keep order of items with single item modification

On Stackoverflow, user asked a question about a data structure that would allow to keep an ordering for a set of items, with the condition of limited memory and only one item can be modified at a ...
428 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 ...
1k views

### On the provability of P versus NP

First of all, my understanding on Gödel's incompleteness theorem (and formal logic in general) is very naive, also is my knowledge on theoretical computer science (meaning only one graduate course ...
174 views

### Proving greedy algorithm is optimal for a scheduling problem

First, the problem discription: For a sequence of $4n$ tasks, $a_1a_2\dots a_{4n}$, where $a_i\in\{0,1\}\forall i$, put them sequentially to the tail of one of the two initially empty queues of ...
88 views

### What can we say about a fixed point for a provability predicate in deductively defined theory that satisfies diagonalisation lemma

I am wondering whether this is the right site to ask this question, but since it involves proof and diagonalisation, hopefully it is the right place. I am curious and trying to reason about what ...
181 views

### Explanation of 1-generic to prove undecidability of halting problem

This question is about an answer in question Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ? Bjørn Kjos-Hanssen answer ...
312 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" ...
555 views

### Proofs found by computer

In 1996, a long-standing open problem was solved by a computer; namely, that Robbins algebra and Boolean algebra are the same. The proof was found by an automated theorem prover. Moreover, the known ...
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 ...
2k 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 ...
### 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 ...