# Questions tagged [proof-techniques]

Questions about general methods and techniques for proving multiple theorems. When asking about the proof of a single statement, use tags relating to what the proof is about instead.

520 questions
Filter by
Sorted by
Tagged with
17k views

### Is there a system behind the magic of algorithm analysis?

There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...
17k views

### Solving or approximating recurrence relations for sequences of numbers

In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
62k views

### How to prove that a language is not context-free?

We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....
109k views

### How to prove that a language is not regular?

We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
8k views

### What is coinduction?

I've heard of (structural) induction. It allows you to build up finite structures from smaller ones and gives you proof principles for reasoning about such structures. The idea is clear enough. But ...
72k views

### How to prove a language is regular?

There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular? For instance, if I am given that $L$ is regular, how can I prove that ...
14k views

### How to show that a function is not computable?

I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
12k views

### What are common techniques for reducing problems to each other?

In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as ...
8k views

### Proof that dead code cannot be detected by compilers

I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the quarter,...
6k views

### Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization. While the proof is convincing (I understand each step of ...
2k views

### Why is Relativization a barrier?

When I was explaining the Baker-Gill-Solovay proof that there exists an oracle with which we can have, $\mathsf{P} = \mathsf{NP}$, and an oracle with which we can have $\mathsf{P} \neq \mathsf{NP}$ to ...
25k views

### How to prove greedy algorithm is correct

I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...
774 views

### Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?

Every undecidable problem that I know of falls into one of the following categories: Problems that are undecidable because of diagonalization (indirect self-reference). These problems, like the ...
7k views

### How do I construct reductions between problems to prove a problem is NP-complete?

I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How ...
24k views

### How to prove that a language is context-free?

There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free? What techniques are there to prove this? Obviously, one way is to exhibit ...
My problem is how can I prove that a grammar is unambiguous? I have the following grammar: $$S → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression \mbox{ then } S \mbox{ else } ... 3answers 6k views ### Is it really possible to prove lower bounds? Given any computational problem, is the task of finding lower bounds for such computation really possible? I suppose it boils down to how a single computational step is defined and what model we use ... 4answers 1k views ### Do undecidable languages exist in constructivist logic? Constructivist logic is a system which removes the Law of the Excluded Middle, as well as Double Negation, as axioms. It's described on Wikipedia here and here. In particular, the system doesn't ... 1answer 5k views ### How to prove correctness of a shuffle algorithm? I have two ways of producing a list of items in a random order and would like to determine if they are equally fair (unbiased). The first method I use is to construct the entire list of elements and ... 1answer 5k views ### How to show that L = L(G)? Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ... 3answers 3k views ### Is there an algorithm that provably exists although we don't know what it is? In mathematics, there are many existence proofs that are non-constructive, so we know that a certain object exists although we don't know how to find it. I am looking for similar results in computer ... 3answers 3k views ### How to show two models of computation are equivalent? I'm seeking explanation on how one could prove that two models of computation are equivalent. I have been reading books on the subject except that equivalence proofs are omitted. I have a basic idea ... 2answers 5k views ### How to describe algorithms, prove and analyse them? Before reading The Art of Computer Programming (TAOCP), I have not considered these questions deeply. I would use pseudo code to describe algorithms, understand them and estimate the running time only ... 1answer 13k views ### How do I write a proof using induction on the length of the input string? In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however ... 1answer 672 views ### Rigorous proof for validity of assumption n=b^k when using the Master theorem The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we ... 1answer 360 views ### Solving divide & conquer reccurences if the split-ratio depends on n Is there a general method to solve the recurrence of the form: T(n) = T(n-n^c) + T(n^c) + f(n) for c < 1, or more generally T(n) = T(n-g(n)) + T(r(n)) + f(n) where g(n),r(n) are some ... 4answers 495 views ### Showing that a problem in X is not X-Complete The Existential Theory of the Reals is in PSPACE, but I don't know whether it is PSPACE-Complete. If I believe that it is not the case, how could I prove it? More generally, given a problem in some ... 1answer 4k views ### Languages that satisfy the pumping lemma but aren't regular? Given a regular language L, then it is easy to prove that there is a constant N such that is \sigma \in L, with \lvert \sigma \rvert \ge N there exist strings \alpha, \beta and \gamma ... 5answers 5k views ### How to prove a problem is NOT NP-Complete? Is there any general technique for proving a problem NOT being NP-Complete? I got this question on the exam that asked me to show whether some problem (see below) is NP-Complete. I could not think of ... 2answers 806 views ### Confluence proof for a simple rewriting system Assume we have a simple language that consists of the terms: \mathtt{true} \mathtt{false} if t_1,t_2,t_3 are terms then so is \mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 ... 2answers 5k views ### Proving a binary tree has at most \lceil n/2 \rceil leaves I'm trying to prove that a binary tree with n nodes has at most \left\lceil \frac{n}{2} \right\rceil leaves. How would I go about doing this with induction? For people who were following in the ... 2answers 12k views ### Master theorem not applicable? Given the following recursive equation$$ T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$we want to apply the Master theorem and note that$$ n^{\log_2(2)} = n.$$Now we check the first two cases for ... 2answers 1k views ### How to deal with arrays during Hoare-style correctness proofs In the discussion around this question, Gilles mentions correctly that any correctness proof of an algorithm that uses arrays has to prove that there are no out-of-bounds array accesses; depending on ... 0answers 313 views ### Proof of PCP theorem I am reading the proof of PCP theorem in Proof Verication and Hardness of Approximation Problems. The following paragraph appears in section 3 (page 4), "Outline of the Proof of the Main Theorem". ... 4answers 484 views ### What are common formal techniques for proving functional code correct? I want to provide proofs for parts of a Haskell program I'm writing as part of my thesis. So far however, I failed to find a good reference work. Graham Hutton's introductory book Programming in ... 3answers 2k views ### How do I verify that a DFA is equivalent to a NFA? I'm learning how to convert NFAs to DFAs and I want to make sure I'm doing it right. Obviously, going back in the other direction isn't a thing. Does anyone know of an algorithm to check that a DFA is ... 1answer 2k views ### A pumping lemma for deterministic context-free languages? The pumping lemma for regular languages can be used to prove that certain languages are not regular, and the pumping lemma for context-free languages (along with Ogden's lemma) can be used to prove ... 2answers 727 views ### Can we show a language is not computably enumerable by showing there is no verifier for it? One of the definitions of a computably enumerable (c.e., equivalent to recursively enumerable, equivalent to semidecidable) set is the following: A \subseteq \Sigma^* is c.e. iff there is a ... 3answers 1k views ### Is it possible to prove thread safety? Given a program consisting of variables and instructions which modify these variables, and a synchronization primitive (a monitor, mutex, java's synchronized or C#'s lock), is it possible to prove ... 3answers 3k views ### Show that there are infinitely more problems than we will ever be able to compute I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot ... 2answers 1k views ### Proof of non-regularity, based on the Kolmogorov complexity In class our professor showed us 3 methods for proving non-regularity: Myhill–Nerode theorem Pumping Lemma for regular languages Proof of non-regularity, based on the Kolmogorov complexity Now the ... 3answers 451 views ### Proving the language which consists of all strings in some language is the same length as some string in another language is regular So I've been scratching my head over this problem for a couple of days now. Given some language A and B that is regular, show that the language L which consists of all strings in A whose ... 2answers 2k views ### Providing Tight Example in Approximation Algorithm Analysis Let's say I found a 2-approximation algorithm for a certain problem and I want to show that the analysis is tight. Do I now need to come up with an example of generic size n or does it suffice to ... 1answer 6k views ### How to use adversary arguments for selection and insertion sort? I was asked to find the adversary arguments necessary for finding the lower bounds for selection and insertion sort. I could not find a reference to it anywhere. I have some doubts regarding this. I ... 3answers 459 views ### Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup I tried to prove that the following language is recursive: for \Sigma=\{0,1\}, k a positive integer:$$ L_k= H_{\mathrm{TM},\varepsilon}\cap \Sigma^k $$where H_{\mathrm{TM},\varepsilon}=\{\... 3answers 637 views ### Can a Minimum Possible Efficiency be proven? Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be? For example, lets take the problem of sorting an array. Many of the ... 4answers 960 views ### Questions about amortised analysis As a preperation of an exam about algorithms and complexity, I am currently solving old exercises. One concept I have already been struggling with when I encountered it for the first time is the ... 2answers 3k views ### Mapping Reductions to Complement of A_{TM} I have a general question about mapping reductions. I have seen several examples of reducing functions to A_{TM} where A_{TM} = \{\langle M, w \rangle : \text{ For } M \text{ is a turing machine ... 3answers 6k views ### Recurrence relation for time complexity T(n) = T(n-1) + n^2 I'm looking for a \Theta approximation of$$T(n) = T(n-1) + cn^{2}$$This is what I have so far:$$ \begin{align*} T(n-1)& = T(n-2) + c(n-1)^2\\ T(n) &= T(n-2) + c(n-1) + cn^2\\[1ex] T(n-2)...
I have developed the following pseudocode for the sum of pairs problem: Given an array $A$ of integers and an integer $b$, return YES if there are positions $i,j$ in $A$ with $A[i] + A[j] = b$, NO ...