# Questions tagged [proofs]

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

20 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
• 233
208 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-...
• 549
316 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 ...
• 281
179 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 ...
• 59
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 ...
171 views

### Randomly Discovered Algorithm/Counterexample

I was reading Scott Aaronson's blog, and one of the comments sparked a question. "if P!=NP, this would be a general, conceptual result, so you’d expect the proof to be explanatory and in particular ...
• 1,082
215 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 ...
• 131
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 ...
• 239
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. \label{eq:nip_obj} \min_{x \in \Phi} \sum_{i = 1}^n ...
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 ...
• 21
1 vote
69 views

### Looking for reference proving polynomial-time bounds for A* search under specific conditions

In the textbook "Artificial Intelligence - A Modern Approach" (Russel, Norvig), it mentions that a sufficient criteria for the A* search algorithm to complete in polynomial time is for the heuristic ...
1 vote
117 views

### Minimum size counter-example in a 2-machine scheduling problem proof

I'm confused about something in the main proof in this paper (sorry that it's behind a paywall, but I assume many people on here have access to such things through their university and my posting the ...
• 111
1 vote
370 views

### Equational Logic and First Order Predicate Logic

I am interested in using Equational Theories (ET) together with Equational Logic (EL) found in algebraic specification languages such as CafeOBJ . I wish to use ET+EL to represent and prove sentences ...
• 179
1 vote
213 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 ...
• 111
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/...
27 views

### How can I show that {a,b}∗ & {a,b,c}∗ are in an equivalence relation using the CBS theorem?

I am perplexed about how can I use the CBS theorem to prove that $\{a,b\}^* \cong \{a,b,c\}^*$. I know that for an injection $h : \{a,b,c\}^* \rightarrow \{a,b\}^*$ we can use two-letter codes for a,...
61 views

### A fundamental question about the proof by induction in session types

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}~~ \...
• 109
210 views

### Correctness proof of recursive-descent recognizer

Let G be a grammar that contains no left-recursive rules, and we use a recursive-descent recognizer that uses full backtracking, using list of results for example, to recognize strings of G. How ...
• 376
I'm currently investigating a family of temporal relations called 'Ordered Horn' ($OH$ for short). This class was introduced in 'Reasoning about Temporal Relations: A Maximal Tractable Subclass of ...