Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
44 votes

How to prove greedy algorithm is correct

Ultimately, you'll need a mathematical proof of correctness. I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a ...
D.W.'s user avatar
  • 160k
42 votes
Accepted

Why are mathematical proofs so hard?

I feel like i am memorizing the proofs rather than learn how to prove You can't learn "how to prove". "Proving" is not a mechanical process, but rather a creative one where you ...
Tom van der Zanden's user avatar
31 votes
Accepted

Proving Equivalence of Two Regular Expressions

One way to prove that two regular expressions $r_1,r_2$ generate the same language is to show both inclusions: Show that if $w$ is generated by $r_1$ then it is generated by $r_2$. Show that if $w$ ...
Yuval Filmus's user avatar
20 votes

Does contradiction definitively prove nonexistence

A proof is a proof, even if the system you work in is inconsistent. So if you prove that the existence of a decider leads to contradiction, you have proved that such a decider does not exist. If in ...
Andrej Bauer's user avatar
  • 30.5k
18 votes

False proofs that look correct

One of my favourites is the "brothers paradox": https://en.wikipedia.org/wiki/Boy_or_Girl_paradox I tell it as I learned it*, as follows: in a village, each family has two children, elder ...
Shaull's user avatar
  • 17.2k
16 votes
Accepted

Prove that A** = A*, where A is a language over Σ*

Since $L \subseteq L^*$ for all $L$, we have $\mathcal{A}^* \subseteq \mathcal{A}^{**}$. In the other direction, suppose that $w \in \mathcal{A}^{**}$. Then there exists an integer $n \geq 0$ and ...
Yuval Filmus's user avatar
16 votes

False proofs that look correct

Merge-sort can be done in linear time! Indeed, the time complexity to sort a list or array of length $n$ verifies$^{(1)}$: $$T(n) = T\left(\left\lfloor\frac{n}2\right\rfloor\right) + T\left(\left\...
Nathaniel's user avatar
  • 15.7k
14 votes

How to prove greedy algorithm is correct

I will use the following simple sorting algorithm as an example: ...
adrianN's user avatar
  • 5,951
13 votes

Show that there are infinitely more problems than we will ever be able to compute

Reformulating in a more mathematically precise way, what the lecturer is trying to say is this: Any algorithm can be (uniquely) encoded as a finite string of bits, and any finite string of bits (...
dkaeae's user avatar
  • 5,027
13 votes
Accepted

Is every unambiguous grammar regular?

The following grammar is unambiguous yet generates a non-regular language: $$ S \to aSb \mid \epsilon $$
Yuval Filmus's user avatar
12 votes
Accepted

Proof that TAUT is coNP-complete (or that a problem is coNP-complete if its complement is NP-complete)

I take it that we call $TAUT$ the problem of given a DNF formula, decide if it is a tautology (if you do not want to restrict to DNF, this will still work as this only makes the problem more general). ...
holf's user avatar
  • 946
12 votes
Accepted

Naive argument that P ≠ NP

The error in your argument is the claim Nothing is known a priori about the function $f$, (...) so it is necessary to plug in all $2^n$ values. , which is simply false. I will demonstrate why it ...
Discrete lizard's user avatar
  • 8,248
12 votes
Accepted

Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

No, it's not possible. Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination. Then there would be some $n$ such that this always terminates after $n$ coin flips. Let $S$...
D.W.'s user avatar
  • 160k
12 votes

Why are mathematical proofs so hard?

As other authors have mentioned, partly because proofs are inherently hard, but also partly because of the cold fact that proofs are not written for the purpose of teaching, even in most textbooks. ...
apen's user avatar
  • 369
11 votes
Accepted

Show that there are infinitely more problems than we will ever be able to compute

If I understand you correctly, your question is — why a solution can be encoded by a natural number and a problem with a real number. (I assume that you understand the next phase of the proof ...
royashcenazi's user avatar
11 votes

Why are mathematical proofs so hard?

I can certainly recommend the book of G. Polya's, How to Solve It. It is a standard classic, not to be missed. There is a newer book How to Read and Do Proofs: An Introduction to Mathematical Thought ...
Elliot's user avatar
  • 211
10 votes

How to prove that a language is not regular?

Following the answer here, I will describe a method of proving non-regularity based on Kolmogorv complexity. This approach is discussed in "A New Approach to Formal Language Theory by Kolmogorov ...
Ariel's user avatar
  • 13.4k
9 votes

Solving or approximating recurrence relations for sequences of numbers

After checking this post again, I'm surprised this isn't on here yet. Domain Transformation / Change of Variables When dealing with recurrences it's sometimes useful to be able to change your ...
ryan's user avatar
  • 4,511
9 votes

Solving or approximating recurrence relations for sequences of numbers

There may be times when you come across a strange recurrence like this: $$T(n) = \begin{cases} c & n < 7\\ 2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + cn & n\geq 7 \end{...
ryan's user avatar
  • 4,511
9 votes

Prove that if f ∉ ω(g) →f∈O(g)

The claim is not true (unless you add some "nice" conditions on the functions). Take, for example, the functions $g(n)=n$, and consider the following function $f$: on the even numbers, we'll take $f(...
Shaull's user avatar
  • 17.2k
9 votes
Accepted

Proof of non-regularity, based on the Kolmogorov complexity

To my knowledge, this is not one of the "classical" approaches used to characterize regular languages. This approach is discussed in "A New Approach to Formal Language Theory by Kolmogorov Complexity"...
Ariel's user avatar
  • 13.4k
9 votes
Accepted

Why proving programs correctness doesn't have the same importance as algorithms analysis or the theory of computation in practice?

On the contrary, it's certainly important practice, and is a huge area of research! Perhaps a better question might be, "why is proving programs correct not common in practice, or not a main feature ...
Joey Eremondi's user avatar
9 votes

False proofs that look correct

I have often seen among undergraduates that they believe that the heaps are constructed in $\Theta(n \log n)$ time. The standard algorithm for that is to insert an element to a heap one after another. ...
Inuyasha Yagami's user avatar
9 votes

False proofs that look correct

This one is regarding $\mathsf{FPT}$ time algorithm. Suppose an algorithm has time complexity of: $O((\log n)^k \cdot n^{O(1)})$. Is it an $\mathsf{FPT}$ time algorithm in parameter $k$? Well ...
Inuyasha Yagami's user avatar
8 votes

How to prove a language is regular?

Another method, not covered by the answers above, is finite automaton transformation. As a simple example, let us show that the regular languages are closed under the shuffle operation, defined as ...
Yuval Filmus's user avatar
8 votes

How to prove that a language is not regular?

In the case of unary languages (languages over an alphabet of size 1), there is a simple criterion. Let us fix an alphabet $\{ \sigma \}$, and for $A \subseteq \mathbb{N}$, define $$ L(A) = \{ \sigma^...
Yuval Filmus's user avatar
8 votes
Accepted

Why does this not prove $P\neq NP$?

What Fiorini et al. show is the following: The TSP polytope $P_n$ over $n$ points is a polytope in $\binom{n}{2}$ dimensions whose vertices correspond to all Hamiltonian cycles in $K_n$ (the complete ...
Yuval Filmus's user avatar
8 votes
Accepted

Does a Haskell program count as an inductive proof?

The statement is not true as stated. Even if we imagine a Haskell-like language where all functions terminate and values are non-bottom, only some programs would correspond to inductive proofs (as ...
Derek Elkins left SE's user avatar
8 votes

Naive argument that P ≠ NP

The answer is simple, many times the naive impression is wrong, and one can find a more clever method to solve the problem. This actually happens a lot in computer science. Clearly one cannot share ...
Ariel's user avatar
  • 13.4k
8 votes
Accepted

The law of excluded middle and decidability

You are conflating computationally decidable with logically decidable. A (closed) formula, $\varphi$, is logically decidable iff $\vdash\varphi$ or $\vdash\neg\varphi$, i.e. if $\varphi$ is derivable ...
Derek Elkins left SE's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible