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
-1
votes
2answers
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,...
4
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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: ...
1
vote
1answer
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 ...
1
vote
0answers
299 views

Given a context free grammar, prove if the grammar is ambiguous

Here is a context free grammar that I have been given for practice: Grammar $G = (V,\Sigma,R,S)$ where $V$ is $\{S,A,B,a,b,c\}$ and $\Sigma$ is $\{a,b,c\}$. $R$ has the following rules: $$\begin{...
2
votes
1answer
317 views

Prove the equivalence between a CFG and a Context free language

I have to prove that the language $L=\{a^ib^j:2i=3j+1\}$ and the CFG G with the following rewrite rules: $S\rightarrow a^2Tb$ $T\rightarrow a^3Tb^2 |\epsilon$ are equivalent to each other. I'm ...
5
votes
2answers
150 views

Nominal unification: How this lemma is proved?

I was reading nominal unification paper. I could not understand the proof of a lemma. The paper is here nominal unification. The lemma is following. $\sigma$ is a substitution, $\pi$ is a permutation ...
4
votes
1answer
361 views

How to prove equivalence relation in this case?

I am working on $\lambda$-terms and trying to prove the $=$ is an equivalence relation on $\lambda$-terms. My problem is proving reflexive relation. $\frac{}{\theta \vdash x = x}$ $\frac{ \theta,x \#...
3
votes
2answers
96 views

what is routine induction?

I read a paper which mentioned routine induction many times. But when I google it, there are nothing showed up. I think routine induction means the induction on the structure, analyzing possible ...
3
votes
1answer
1k views

Every LEFT-RESET Turing machine has an equivalent conventional Turing machine

I am working on a proof of the theorem that every LEFT-RESET Turing machine has an equivalent conventional, single tape Turing machine. The transitions for the LEFT-RESET Turing machine are {Right, ...
1
vote
2answers
715 views

Proof Idea: How to prove the intersection of regular language and CFL is a CFL?

I know that the intersection of a regular language and a context free language is a context free language. I've seen this fact proven on here and other websites. However, after spending hours reading ...
2
votes
1answer
896 views

CFL and inverse homomorphism

I found a proof that shows CFL is closed under inverse homomorphism. First of all the Definition of an homomorphism and its inverse: $h: \Sigma^{*} \rightarrow \Delta^{*} \ \ \ h(L) = \{h(w) |w \in ...
2
votes
0answers
117 views

Formalizing an intuitive linear programming proof

My professor has asked me to prove the following: Prove that we can use an algorithm for linear programming to solve linear inequality feasibility problems. The number of variables and ...
2
votes
2answers
1k views

Proving at least $n-1$ comparisons are needed to test if an array is sorted

so I need to prove the following: Prove that $n-1$ comparisons are sometimes necessary to test whether an array with $n$ distinct elements is sorted in increasing order, for any $n \geq 1$. The ...
2
votes
1answer
182 views

Is the search for a k-Hamiltonian Path NP-hard?

A $k$-Hamiltonian Path is an Hamiltonian Path where each node (but the last $k$ nodes on the path) is connected to his $k$ successors, and the last $k$ nodes are connected to all of their successors. ...
0
votes
1answer
488 views

Support of a codeword in a binary linear code proof

Let $C$ be the binary linear code with the following generator matrix $G= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & ...
1
vote
1answer
45 views

Linear Bound Automaton Power

Please tell me is their deterministic linear bound automaton same power as non-deterministic linear bound automaton to recognize any language?
1
vote
1answer
2k views

Proving that a problem is in NP

I have an assignment in which the problem, $D$, is simple but, once found, easy to check. Is it enough to prove that a solution $x$ can be checked in polynomial time to prove that $D \in NP$? (The ...
0
votes
0answers
248 views

Writing a constructive proof for closure of a regular language under homomorphism

I've spend the last few days searching online for an example of a constructive proof of regular languages being closed under homomorphism, but I have not seen one. I am mostly unsure of how to show ...
1
vote
2answers
60 views

Can you apply the induction hypothesis to its outcome?

Assume a well-founded relation $<$ over a set $S$ and a property $P$ on $S$ such that: $P$ holds for all minimal elements of $S$. For every $b \in P$ and $a < b$ we have: if $P(a)$ then there ...
2
votes
2answers
127 views

The floor function [closed]

How do I prove or disprove the following statements: $$(a) ∀n ∈ \mathbb N, ∃k ∈ \mathbb N, ∀x ∈ \mathbb R , \lfloor nx \rfloor − n \lfloor x \rfloor ≤ k$$ and $$ (b)\exists k \in \mathbb N, \forall n \...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
2answers
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 ...
1
vote
1answer
6k views

Pumping Lemma: 1^n^2 is not regular

I am attempting to prove via the pumping lemma that $1^{n^2}$ is not a regular language. I started with $w = 1^{p^2}$ I then divided $w$ into $xyz$, where: $x = 1^{l}$ $y = 1^{m}$ $z = 1^{{p^2}-...
2
votes
1answer
321 views

Analysis of the long division algorithm in the Knuth book (Seminumerical algorithms) 1

I've been reading through the long division algorithm exposed in the Knuth book for a week and I still miss some details. There's an implementation of such algorithm in "Hacker's Delight" by Warren, ...
2
votes
2answers
348 views

How can I prove that a cryptography algorithm is a pseudo-random number generator?

I have read about cryptography prgs. If I have a generator G(x1,x2...,xn)= x1,x2,...,xn, x1&x2...&xn , how can I prove that it is a prg or prove it is not? Is there some principles I have ...
0
votes
1answer
161 views

If $L\in\mathrm{NP}$ is $\mathrm{coNP}$-complete, then $\mathrm{coNP}=\mathrm{NP}$

The problem in the title is to be proven, and while proving $\mathrm{coNP}\subset\mathrm{NP}$ is rather clear given the assumptions (see below), I fail to see a way to prove $\mathrm{NP}\subset\mathrm{...
3
votes
2answers
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 ...
5
votes
1answer
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, ...
3
votes
1answer
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 ...
4
votes
1answer
437 views

Prove foldl fusion law

I have proven the foldr Fusion Law as follows: Given f is strict, f a = b and ...
3
votes
1answer
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, ...
7
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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?
6
votes
1answer
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 ...
1
vote
1answer
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.
3
votes
0answers
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 ...
4
votes
1answer
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 ...
1
vote
0answers
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, ...
2
votes
1answer
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 ...
2
votes
1answer
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$ ...
2
votes
2answers
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 ...
7
votes
1answer
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 ...
1
vote
1answer
95 views

Prove that at least as many edges as vertices implies a cycle

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$ ...
6
votes
2answers
725 views

Proof (by contradiction) of the emptiness problem

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

1
3 4
5
6 7
12