What's the deal with Deno? We talk with a major contributor to find out. 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.

592 questions
Filter by
Sorted by
Tagged with
122 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 ...
52 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, ...
19 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 ...
194 views

### Proof that an almost complete binary tree with n nodes has at least $\frac{n}{2}$ leaf nodes

I'm having some trouble proving what my title states. Some textbooks refer to almost complete binary trees as complete, so to make myself clear, when I say almost complete binary tree I mean a binary ...
203 views

### How can I prove that my greedy algorithm for least guards is optimal?

This is the problem: An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of ...
269 views

### Making Candies - HackerRank question - proof of optimality of a greedy approach

I stumbled across this question in HackerRank: Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies. Karl just started a ...
180 views

36 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 ...
1k 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, ...
635 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 ...
101 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. ...
96 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)$. ...
252 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 ...
500 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 ...