# Questions tagged [proofs]

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

84 questions
Filter by
Sorted by
Tagged with
60 views

### What's the difference between "modular" and "compositional"?

When talking about reducing complexity in a software system, we often talk about making it "modular" by breaking it up into multiple modules that are all linked together to form the overall ...
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 ...
185 views

### Halting problem proofs that do not utilise self-reference or diagonalization

Are there any proofs of the Halting problem that do not involve any self-reference, and diagonalization (or any diagonal argument) whatsoever? All the duplicate questions I have come across end up ...
119 views

### Sources that prove solving 2-SAT with DP takes linear time

Would anyone have any sources that describe/an explanation of how solving 2-SAT using dynamic programming takes a linear amount of time? Can't seem to find a text that proves it in detail/formality. ...
20 views

### Proof that Sufficiency and Caliberation by group are equivalent notions

I am currently reading through the Fairness and Machine Learning book and I have a problem understanding the proof of Proposition 1 in Chapter 3 (titled Classification) (https://fairmlbook.org/...
1 vote
198 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}$....
104 views

61 views

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 ...
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 ...
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 ...
927 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 ...
193 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 ...
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: ...
399 views

### Where is the quote "Informal proofs are algorithms, formal proofs are code" from?

Does anyone know the origin of the quote, Informal proofs are algorithms; formal proofs are code. Its made in Benjamin C. Pierce et al.'s Software Foundations.
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 ...
1k 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 ...
69 views

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

Given is the sorting algorithm Bubblesort ...
1 vote
324 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 ...
682 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 ...
256 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 ...
1 vote
137 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 ...
6k 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, ...
447 views

### Paxos made simple, invariant P2c

I am reading Leslie Lamport's Paxos Made Simple paper. Can someone explain why $P2^c$ implies $P2^b$? $P2^b$ If a proposal with value $v$ is chosen, then every higher-numbered proposal issued ...
667 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, ...
216 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 ...