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
10
votes
0
answers
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
6
votes
0
answers
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
5
votes
0
answers
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
4
votes
0
answers
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
3
votes
0
answers
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 ...
3
votes
0
answers
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
3
votes
0
answers
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
2
votes
0
answers
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
0
answers
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 ...
- 185
1
vote
0
answers
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
0
answers
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 ...
- 415
1
vote
0
answers
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
0
answers
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
0
answers
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
0
votes
0
answers
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/...
0
votes
0
answers
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,...
0
votes
0
answers
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
0
votes
0
answers
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
0
votes
0
answers
278
views
Famous computer science results which correctness is uncertain?
I am asking the following: which of the 'famous' computer science results have been thoroughly checked, and for which ones is the correctness still uncertain?
I understand that some proofs are hard ...
0
votes
0
answers
93
views
A self-contained proof that OrdHorn relations are tractable?
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 ...
- 1,292