# Questions tagged [proofs]

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

89 questions
Filter by
Sorted by
Tagged with
107 views

### If I want to end math, where should I start?

I'm a PhD in math, but I'm not good. I'm familiar with Riemannian geometry, a little partial differential equations, and a little algebraic topology. And the other undergraduate courses of math (I ...
46 views

### Is this variant of Facilities location problem a NP-hard problem?

Given a set of locations $P=\{p_1,p_2,\dots\}$ and a set of facilities $F=\{f_1,f_2,\dots\}，|F|\ge k$ on a plane. We want to partition the facilities into $k$ disjoint subsets (each subset has at ...
46 views

### Proving the Equivalence of REGEX r^n and r^{..n} when r Is Nullable

Im seeking clarification and a rigorous proof regarding the equivalence of r^n and r^{..n} in the context of formal languages, particularly when r is nullable. To clarify the terminology: r denotes ...
1 vote
35 views

### Overlap operator for simple ( regex-like ) Patterns

( Introduction ) Some Notation lower case letters, $a, b, c$ will be used to denote single symbols Upper case letters, $P, Q, R$ will be used to denote string of symbols $a\!:\!S$ means a string ...
33 views

### Combining different length epsilon-ADU hash function families

For context, an $\epsilon$-almost delta universal ($\epsilon$-ADU) hash function family $\mathcal{H} = \{h : M \to D\}$ hashes inputs from $M$ to digests in $D$ such that for any distinct $m, m' \in M$...
155 views

### Conversion between NP certificates

This might be a well-known fact, but I can't convince myself of whether this is true. Suppose I have some NP language and two different verifying procedures V and V' for L. For any x in L, is it the ...
66 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 ...
216 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 ...
139 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. ...
41 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/...
116 views

64 views

I have a question about proof by induction in the domain of session types. Let's assume we have the following lemma: $$\text{Let}~ \Gamma \vdash P : T. ~~\text{If } P = \mu X. Q ~~\text{then}~~ \... 8 votes 1 answer 138 views ### Construction of arbitrary functions with exponential-size MODp \circ MODq circuits It is mentioned in multiple papers ,  that MODp \circ MODq circuits for two distinct primes p, q can compute arbitrary functions in exponential size. However,  provides no citation for ... 4 votes 0 answers 180 views ### Any problems for which we know the complexity, but no algorithms with the same time? I suddenly found myself wondering if there are any problems for which the complexity (time or space or anything else) is proven, say to be O(n^2), but for which the best known algorithms are worse ... 4 votes 2 answers 109 views ### Proving that a given formula in LTL is the smallest way to express it I am looking for a way to prove that a given LTL formula is expressed with the fewest number of temporal operators possible. I would like to do this to compare the expressive length with other ... 3 votes 1 answer 366 views ### How hard is this combinatorial optimisation problem? Suppose we have multiple intervals R_1,R_2,...,R_i of non-negative integers. These intervals may overlap and we use R_h(\mathrm{median}) to denote the median integer in the h-th interval R_h, ... 4 votes 3 answers 415 views ### Proving proof system properties within the proof system itself? While reading about Frege proof systems in , I came across the completeness theorem and its proof, which involves a few lemmas introduced first. Here are the first two of those lemmas:$$\begin{... 988 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 ...
203 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 ...
1 vote
207 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}$....
70 views

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

Given is the sorting algorithm Bubblesort ...
1 vote
325 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 ...
693 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 ...
260 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
140 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 ...
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 ...
704 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, ...
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 ...