8
votes
Is Goedel's 1st theorem not algorithmically derivable?
Your reasoning is incorrect.
It is true that your hypothetical "proof deriver" cannot derive all true statements. No proof derivation system can, and indeed, it is not even possible to express the ...
- 7,754
5
votes
Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$
An alternative solution still using domain transformation/change of variables.
$$T(n) = T(\sqrt{n}) + \log \log n$$
1. Let $m = \log n$
We can then define a new function $S$ based on how $m$ ...
- 4,381
5
votes
Accepted
Every AVL tree may be red black tree
Your proof produces a tree in which all nodes are colored black. It doesn't necessarily satisfy the "black height" rule:
Every path from a given node to any of its descendant NIL nodes contains the ...
- 271k
4
votes
If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$?
If $f = O(g)$, then
$$\exists n_0. \exists c. \forall n. (n > n_0 \rightarrow f(n) \le c g(n))$$
The negation of this statement is
$$\forall n_0. \forall c. \exists n. (n > n_0 \land f(n) >...
- 8,947
4
votes
Accepted
Simpler proof of Rabin's Compression Theorem?
It is hard to answer this question since it is hard to find a formal statement of Rabin's compression theorem. Here is one from the book Complexity Theory and Cryptology: An Introduction to ...
- 271k
4
votes
Accepted
Proving the loop invariant for a simple program in Hoare logic
Your invariant, together with the negation of the loop condition, is not strong enough to imply your postcondition. Try adding an additional conjunct to the invariant which, together with $\neg\ i<...
- 2,148
4
votes
Accepted
Why is this a proof by contradiction for this algorithm? Isn't this a direct proof instead?
You seem to think the structure of the proof is:
suppose the algorithm is incorrect;
prove that the algorithm is, in fact, correct;
this contradicts 1., so the algorithm is correct.
That's almost, ...
- 80.5k
4
votes
Accepted
Show $\{0^𝑚1^𝑛|𝑚≠𝑛\}$ is not regular
Try to express in natural language what $\overline{L}$ contains; that is, what words $L$ doesn't contain. Most obviously, it's "words of the form $0^m0^n$, with $m = n$." However, it also ...
- 124
3
votes
Accepted
Optimizing coin splitting - Is this algorithm as fast as I think?
You have made significant progress on this problem. Your final conclusion, "the overall algorithm asymptotically requires $\Omega(n^2)$ steps" is likely to be correct as well.
Analysis of Your ...
- 35.3k
3
votes
Accepted
Question about proving that Rado's function is non-computable
Thanks for the clarification! I really misinterpreted your question.
Okay, so we have the computable function $f$, the also computable function $F$ that is based on $f$, and the Turing machine $M_F$ ...
- 173
3
votes
Accepted
Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$
We can expand the recursion (ignoring the constant 10) as follows:
$$
\begin{align*}
T(n) &= \log \log n + \log \log n^{1/2} + \log \log n^{1/4} + \log \log n^{1/8} + \cdots \\ &=
\log \log n +...
- 271k
3
votes
Accepted
If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$?
Here is a simple counterexample:
$$
\begin{align*}
&f(2m) = 2^{2^{4m}} & &g(2m) = 2^{2^{4m+1}} \\
&f(2m+1) = 2^{2^{4m+3}} & &g(2m+1) = 2^{2^{4m+2}}
\end{align*}
$$
The first ...
- 271k
3
votes
Accepted
Is this proof for showing that $EQ_{CFG}$ is co-Turing-recognizable incorrect?
In this context, lexicographic order means:
First order by length.
Within each length, order lexicographically.
You're saying that the proof is incorrect, but in fact it is only inaccurate in that ...
- 271k
3
votes
Why is this a proof by contradiction for this algorithm? Isn't this a direct proof instead?
It's a proof by contradiction that could easily be rewritten as a direct proof.
To rephrase it as a direct proof, we divide it into two claims:
$max$ is an element of $A$.
$max \geq A[j]$ for all $j$...
- 271k
3
votes
Number of possible heaps on $\{1,...,2^h-1\}$
The definition you give looks like the definition of a complete tree. With the restriction that nodes are in $[\![1, 2^h-1]\!]$, then it is also a perfect tree of height $h$.
Instead of looking at ...
- 7,534
3
votes
how to prove that log(n!) >= c n log(n) for some c >0?
$n! = n \cdot (n-1) \cdot ... \cdot 1 \ge n \cdot (n-1) \cdot ... \cdot (n/2) \ge (n/2)^{(n/2)}$
so
$\log(n!)≥c\cdot n\cdot\log n$ for $c \ge 1/2$
- 221
3
votes
Accepted
$\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS
You have caught an instance of the infamous off-by-one error in that popular textbook whose name we shall not mention again.
To repeat, it is correct that "the cost $c_1=1$, $\Phi_0=0$", &...
- 35.3k
3
votes
Not understanding this way of proving undecidability of the termination problem
This is a very succinct way of presenting the contradiction argument, and I strongly recommend you read a textbook on the topic, or some detailed explanations. There are tons of resources that explain ...
- 16.5k
3
votes
Accepted
Disprove: if L is decidable then Prefix(L) is decidable
It is correct that if $L$ is decidable language $\text{Prefix}(L)$ can be undecidable. The language $L$ given in the question is a concise example of a decidable language the prefix language of which ...
- 35.3k
2
votes
If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$?
Here's an explicit construction of $f$ and $g$ such that neither $f=O(g)$ nor $g=O(f)$. To make the calculations slightly easier, I've chosen $g$ to be increasing and $f$ to be nondecreasing (namely, $...
- 14.7k
2
votes
Accepted
Algorithm to recognize Strongly Regular Graph (SRG)
There is a trivial $O(kn^2)$ algorithm:
Choose a vertex $v$ and calculate its degree $k$. Then verify that all other vertices have degree $k$.
Choose some neighbor $w$ of $v$ and calculate the number ...
- 271k
2
votes
Accepted
Proof Review: Integer Factorization is in NP
You are missing something.
If you are given what is supposed to be a factorisation of a number x, it's not enough to show that the product of those numbers is x. You also have to prove that all the ...
- 25.9k
2
votes
Accepted
Show that function is not turing-computable?
This proof is correct as written, well done :) Remember this pattern, because an identical proof can be used in a wide variety of similar problems such as rational/irrational numbers and polynomials/...
- 767
2
votes
Universal Lossless Compression?
Then you can compress all $g_j ∈ S_N$, by iterating through $A$ until you find $a_i|f(a_i,g_j)−m>0$.
I'm not sure what the notation means (the pipe here, and also $\#A$ elsewhere), but still: ...
- 71.2k
2
votes
Optimizing coin splitting - Is this algorithm as fast as I think?
Aren't you just overcomplicating things? I'd use an n x n matrix, and a nested loop that finds the result in about five lines of code in O (n^2).
Let b[i,j] = the amount by which you can beat your ...
- 25.9k
2
votes
Is Goedel's 1st theorem not algorithmically derivable?
Our proof deriver enumerates all possible axiomatic systems
But the set of possible axiomatic systems also include the inconsistent systems. On the other hand, the consistent axiomatic systems are ...
- 5,322
2
votes
Optimizing coin splitting - Is this algorithm as fast as I think?
Your algorithm may work, but FWIW it's more conventional to build game trees where the two players' moves form alternating layers of vertices rather than combining one move from each into a single ...
- 2,072
2
votes
Accepted
How to Apply Elementary Axioms from Kleene Star to an Inequality
I assume that in your definition $a \leq b$ iff $a + b = b$.
First, note that if $a \leq b$ and $b \leq a$, then $a = a + b = b + a = b$.
Therefore, in order to show that $a = b$, it is sufficient to ...
- 196
2
votes
Accepted
Minimal paths as solution of a linear program of a special network flow
There is a major flaw in your question: You presented a shortest path formulation and not a special case of a network flow problem.
Your objective function minimizes the cost of the path. The next 5 ...
- 239
Only top scored, non community-wiki answers of a minimum length are eligible