# 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.

544 questions
Filter by
Sorted by
Tagged with
44 views

### Stuck on proof in Coq

This is an exercise from Software foundations for my discrete math & functional programming class. I am a little stuck with the end of the code because it works for the first two examples but it ...
84 views

### Showing on-line P = NP

I have developed a theorem that proposes a method to build algorithms. All the algorithms produced by this method are in P ... they never go up to more than $6(n^{12})$ operations. Following that, I ...
12k views

### Converting context-free grammar to chomsky normal form

I'm trying to prove that the following CFG can be converted to a CNF: S -> aAB A -> aAa A -> bb B -> a Here below is how I've managed so far: Step 1:...
65 views

### Proving that a sum of n zeros are 0

Define a function $\text{zeros} \colon \textsf{nat} \to \textsf{natlist}$ that, given a natural $n$, produces a list of $n$ zeroes. You can use either Coq notation or, if you're comfortable with it, ...
43 views

### Prove that in an optimal code, if the letter frequencies are increasing, the encoding lengths are monotonically decreasing

I am trying to prove that, in an optimal encoding (possibly Huffman?), if letter frequencies are increasing, their encoding lengths are monotonically decreasing. It is intuitive that this makes sense, ...
17 views

### Comparison tree to get a minimum number of comparisons for merging sorted lists

Suppose A is a sorted list of length n and B is a sorted list of length 2. I am asked to ...
1k views

### What approaches are most useful when proving uncomputability of a given function?

I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows: Reduction,...
1k views

67 views

### Proving a first order logic theorem in equational logic with a term rewriting system

I am trying to translate and prove a theorem, originally written in first order logic (FOL), into a combination of equational logic (EL) and Boolean logic (BL) (more precisely a model of Boolean ...
58 views

35 views

### Weaker conjectures to prove in order to arrive at P =/= NP

We know we have a long way to go before we come to a proof of P $\neq$ NP. We also know that this road is studded with minor conjectures that will have to be proved/disproved in order to arrive at the ...
115k 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 ...
196 views

### Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$ [duplicate]

I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, ...
324 views

### Is {a^n: n is a product of exactly two primes} regular?

I am struggling to prove the following question. $L_1 = \{a^n: n \text{ is a product of exactly two primes}\}$ I feel like the language is not regular but I am having trouble proving it. I tried ...
78 views

### Codeword constructed by Huffman's algorithm has average length of at most log n

I am interested in the following question: Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $\log n$, where $n$ is the number of codewords. ...
83 views

### Proving with co-induction principles

I'm going through Adam Chlipala's "Certified Programming with Dependent Types" (available here for convenience), and I'm a bit stuck at internalizing the introduction of co-induction principle for the ...
75 views

### How to justify $f(n) = O(g(n))$ [duplicate]

The following question is in my homework: Is the statement $f(n) = O(g(n))$ true, when $f(n) = n/2 + 4$ and $g(n) = \sqrt{n} + 2\log_2 n + 3$? I understand how $f(n)$ is the upper bound of $g(n)$. ...
199 views

### Proof by reduction and Turing machines [closed]

This is a practice question I have, but I can't wrap my head around it. ............. Let L = {M | M is a TM that halts with exactly two words on its tape in the form Bw1Bw2B}. B = Blank Position the ...
99 views

### How to prove by contradiction that every nonempty hereditary language contains the empty string?

A language L is called hereditary if it has the following property: For every nonempty string x in L, there is a character in x which can be deleted from x to give another string in L. Prove by ...
65 views

### How to prove $L \notin \texttt{DSPACE}(f)$

I want to prove that a language $L$ is not in $\texttt{DSPACE}(f(n))$, the class of languages that a deterministic Turing machine can decide with fixed tape length of $f(n)$ (wiki). That is, I want to ...
208 views

### Proving that $(a \cup b)^* = (b^*(a\cup\lambda)b^*)^*$?

How would I prove that these two regexes are equal to one another? $$(a \cup b)^* = (b^*(a\cup\lambda)b^*)^*$$ I'm permitted to use the following regular expression identities.
22 views

### Isn't ZKP is a reduction to a hard problem, rather than true zero knowledge?

Take for example "Hamiltonian cycle for a large graph". The proof works by starting with a graph G that contains a hamiltonian cycle, then constructing an isomorphic graph H, and then either showing ...
862 views

### How to prove a greedy algorithm that uses the longest increasing subsequence?

Here is the thing, I am solving an problem, and I think, say, I am pretty sure that I have the correct algorithm but I haven't been able to prove it because of my lack of practice prooving greedy ...
407 views

### Prove foldl fusion law

I have proven the foldr Fusion Law as follows: Given f is strict, f a = b and ...