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

560 questions
Filter by
Sorted by
Tagged with
199 views

### Is this a valid proof of uncomputability of a function that doesn't use diagonalization?

Let's take the function $f = \{(0,\pi)\}$. If I want to prove that such function is uncomputable I can simply say that calculating $\pi$ from $0$ would necessarily require infinitely many steps,...
410 views

### How to use structural induction to prove law on lists

I want to prove that the following equation holds using structural induction on (finite) lists ...
139 views

### Where I can find example how prove red black tree?

I need prove that any red-black tree with at least two elements obtained through the insertion algorithm has at least one red node. For this, I need use Induction. I don't understand how apply ...
430 views

### Minimal number of states

In a recent IT class we got the task of creating a finite state automaton that accepts only the words "auto" "automarke" "tomaten" and "automaten" and no others. Basically the whole class had no ...
134 views

### Proving laws of take and drop functions using structural induction on lists

I'm trying to prove the following laws using structural induction on (finite) lists: ...
149 views

### Collision resistant Hash function in chaos cryptography

In my earlier Question asked here Help in understanding how to apply nonlinear function in hashing about chaos cryptography, since then I have come across several research papers that apply atleat ...
299 views

2k views

### How would you prove a family of functions is universal?

A set of functions from a universe U of keys to n buckets is universal if for every pair of keys in U, say x and y, such that x != y, the probability of h(x) = h(y) is less than or equal to 1/n, for a ...
926 views

### Red-Black tree height from CLRS

The lemma 13.1 of CLRS proves that the height of a red black tree with $n$ nodes is $$h(n) \leq 2\log_2(n+1)$$ There's a subtle step I don't understand. The property 4 reported at the beginning of ...
414 views

### Prove L = {a = b ⊕ c | a, b, c ∈{0, 1}*} is not regular

Given that language $L = \{a = b ⊕ c \mid a, b, c ∈ \{0,1\}^*, a = b \oplus c\}$, with an alphabet $Σ = \{⊕, =, 0, 1\}$, I need to prove that this language is not regular. The following is as far as I ...
6k views

64 views

### Given the hash of a collection, H(X), can I build a proof that F(X) == Y, without having X?

Given a cryptographic fingerprint of a collection, K == hash(X), an arbitrary function F, and a value ...
58 views

### Is it possible to build short proofs of arbitrary folds over a huge list?

With the use of Merkle Trees, you can prove the presence of an element of a very big list, with an amount of information close to just logarithm of the size of the whole tree. Merkle proofs, thus, ...
921 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 ...
437 views

### Prove foldl fusion law

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

### Do formulas involving fewer repetitions of variables give higher numerical precision?

I'm having some trouble doing SICP exercise 2.15. Please note that this question is not closed related to Lisp. Instead, it's closely related to numerical analysis. Exercise 2.15. Eva Lu Ator, ...
178 views

### Why Church-encoded types aren't sufficient to express inductive proofs?

I've heard some claims that the calculus of constructions without inductive types isn't powerful enough to express proofs by induction. Is that correct? If so, why isn't the Church-encoding sufficient ...
35 views

### Can an alphabet be extended in a reduction proof? (with sample problem)

So I am working on solving a problem on whether following language is decideable: $L = \{n \in \mathbb{N} \mid M_n$ never freezes (for any input)$\}$, where $n$ is the Gödel-number of a Turing ...
162 views

### Proof that language is not context-free with Parikh's theorem

I want to prove that the language $L = \{ a^{n}(ab)^{{n}^{2}}b^{n} \mid n \geq 0 \}$ is not context-free by using Parikh's theorem. My first assumption is that the $(ab)^{{n}^{2}}$ part cannot be ...
71 views

### NFA automata with ϵ moves proof

let's say L is a regular language. And there in an NFA automata with epsilon moves A,in which for every accepting state δ(q,σ)=Ø. How can I prove that there must be an automata A as defined for L?
3k views

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

What are the major causes that makes "Proving Programs correct", not a widely attractive subject? though from it's name, and from what we know from other disciplines (like mathematics) it looks like ...
66 views

### NFA automata with ϵ moves proof

How can I prove that for every NFA with $\epsilon$ moves if $q_0 \in F$ then $\epsilon \in L(A)$? I can't think of any technique since it seems so trivial.
240 views

### Sequence Alignment with general gap penalties: proof of optimal substructure

I am very well-aware of how optimal substructure for pairwise global sequence alignment using the Needleman-Wunsch algorithm works. However, I have merely seen hand-waving explanations for the ...
460 views

### in refutation (resolution) can we use a clause that have been resolved

In resolution if we have a set S composed of three clause C1, C2 and C3 and we want to proof that C4 is derivable from S using refutation: suppose we've resolved C1 and C2 to C5, can we resolve C1 ...
98 views

### Proving an invariant in a recursion using mathematical induction

Given the following pseudocode for function AP(x, y: integer) which returns an integer, ...
212 views

### How do we know that the reduction is correct?

I'm having a really difficult time understanding the logic behind reduction of the halting problems to other problems in order to prove them undecidable. Here's my reasoning: Let's say that we want ...
43 views

### Valid actions of Reductions to NP-Completeness

To my understanding, as long as we can find some polytime function $f$ such that $\forall x:x \in A \Longleftrightarrow f(x) \in B, x\notin A \Longleftrightarrow f(x) \notin B$, it follows that if $A$ ...
359 views

### Knapsack and set cover-like problem

Given $n$ sets $r_1, r_2, \cdots, r_n$ and a number $\delta$ where $0 \le \delta \le 1$. Let $T=\cup_{i=1}^{n}r_i=\{t_1,t_2,\cdots,t_m\}$. Each $t$ has a value $v(t)$, which is given to us. The task ...
106 views

### What is the purpose of interpreting elements in the proof of reduction of PCP to validity decidability problem of predicate logic?

Since my question relates directly to a part of the text from a 2004 book, Logic in Computer Science: Modelling and Reasoning about Systems (2nd Edition) by Michael Huth and Mark Ryan, in order to ...
I am EXTREMELY confused on where to start with this problem. We recently just started learning about graph theory and I don't know where to begin. Prove that in a connected graph G with $p$ ...
I fail to understand the proof of the Emptiness Problem $E_{TM} = \{\langle M \rangle | M$ is a TM and $L(M) = \emptyset\}$ 1) Use the description of $M$ and $w$ to construct $M_1$, which on Input \$...