Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

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.

Filter by
Sorted by
Tagged with
24
votes
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 ...
7
votes
2answers
131 views

Low-degree nodes in sparse graphs

Let $G = (V,E)$ be a graph having $n$ vertices, none of which are isolated, and $n−1$ edges, where $n \geq 2$. Show that $G$ contains at least two vertices of degree one. I have tried to solve this ...
11
votes
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 $...
3
votes
1answer
127 views

An argument for error accumulation during complex DFT

I am doing FFT-based multiplication of polynomials with integer coefficients (long integers, in fact). The coefficients have a maximum value of $BASE-1, \quad BASE \in \mathbb{n},\quad BASE > 1$. ...
4
votes
2answers
4k views

Why is this example a regular language?

Consider this example (taken from this document: Showing that language is not regular): $$L = \{1^n \mid n\text{ is even}\} $$ According to the Pumping Lemma, a language $L$ is regular if : $y \ne ...
7
votes
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 ...
10
votes
2answers
732 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 ...
3
votes
1answer
432 views

Null Characters and Splitting the String in the Pumping Lemma

So I'm really struggling with the pumping lemma. I think most of my problems come from not understanding how you can and can't split the string in a pumping lemma question. Here is an example, take ...
8
votes
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 ...
4
votes
4answers
4k views

Prime number CFG and Pumping Lemma

So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class. I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to ...
48
votes
8answers
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 ...
29
votes
3answers
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 ...
27
votes
2answers
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 ...
11
votes
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 ...
7
votes
4answers
3k views

Loop invariant for an algorithm

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 ...
14
votes
2answers
807 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$ ...
77
votes
10answers
110k 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 ...
18
votes
4answers
496 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 ...
14
votes
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 ...
69
votes
2answers
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 ...
89
votes
5answers
63k 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....