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
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
225 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
368 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
94 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
201 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
294 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
96 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
94 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
497 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 $...
0
votes
0answers
76 views

Boys And Girls Problem. How to prove that the algorithm is correct?

Given that, there are 10 children standing in a circle, 8 of them stand next to a boy, and 4 of them stand next to a girl. If 7 boys and 3 girls stand in the following order: GBGBGBBBBB, then 8 ...
0
votes
0answers
70 views

Showing $L=\{a^ib^jc^k: i,j,k \text{ not all equal}\}$ is a CFL a lemma [duplicate]

In their answer, Janoma proves that $\{a^ib^jc^k:i\neq j,j\neq k,i\neq k\}$ is not context-free using Ogden's lemma, but I haven't learned about Ogden's lemma yet. I wanted to know whether Ogden's ...
2
votes
2answers
106 views

Lambda Calculus Prove Equality Excessive (Haskell-oriented)

I'm on a lambda calculus with parametric polymorphism a la Hindley-Milner Haskell-oriented course and I'm currently facing this exercise which I got stuck on. Prove that $(\forall m\downarrow, n\...
1
vote
1answer
584 views

Proving a language is not context free using the Pumping Lemma

To prove that $L=\{0^m1^n|n \text{ divides } m,\text{ } m,n\gt0\}$ is not a CFG, I applied the pumping lemma. I chose $w=0^{21p}1^{7p}$ for the pumping constant p. By the pumping lemma, $w=xyuvz, |yuv|...
-1
votes
1answer
612 views

Why does russian peasant multiplication work? [duplicate]

can someone provide a proof with induction on why the Russian peasant multiplication work ? if you don't know what that is , here is the algorithm : ...
4
votes
2answers
113 views

Is structural induction on terms applicable when a function is involved?

Assume an evaluation-relation on terms $t \Downarrow v$. If I want to prove correctness of a function $\phi$ w.r.t. evaluation, I have to show that the following implication always holds: $$\frac{\...
8
votes
2answers
1k views

Proof of non-regularity, based on the Kolmogorov complexity

In class our professor showed us 3 methods for proving non-regularity: Myhill–Nerode theorem Pumping Lemma for regular languages Proof of non-regularity, based on the Kolmogorov complexity Now the ...
4
votes
1answer
285 views

Proof that PDA's with different definitions have same expressive power

Let $P$ be a push down automaton $(Q,\Sigma,\Gamma,\delta,q_s,F)$, where $Q$ is the set of states, $\Sigma$ is the input alphabet $\Gamma$ is the stack alphabet $\delta$ is the transition function ...
1
vote
1answer
54 views

Proving that quantum circuits not involving entanglement are inefficient

I heard in a video that it can be proven that quantum circuits not involving entanglement can be efficiently simulated on a classical computer; i.e., that there is no point to building quantum ...
1
vote
0answers
32 views

How to prove that $\lfloor{\sqrt{n}\rfloor} = \Theta(\sqrt{n})$? [duplicate]

It is quite direct to prove that $\lfloor{\sqrt{n}\rfloor} = O(\sqrt{n})$. But how can I prove that $\lfloor{\sqrt{n}\rfloor} = \Omega(\sqrt{n})$?
2
votes
2answers
11k 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:...
2
votes
2answers
874 views

Prove that if f ∉ ω(g) →f∈O(g)

I am trying to prove the statement in the title. I have a hard time proving it is true. The way I go about it is by using the definition of $\omega$: $c\times g(n) < f(n)$; So that if $f \notin \...
0
votes
1answer
399 views

Adding Big-O and little-o notation to get a little-o

Lets suppose that there exists a comparison-based algorithm that turns an arbitrary array to a state $A$ in $o(n\log k)$, and there is another comparison-based algorithm that turns an array in state $...
10
votes
4answers
481 views

What are common formal techniques for proving functional code correct?

I want to provide proofs for parts of a Haskell program I'm writing as part of my thesis. So far however, I failed to find a good reference work. Graham Hutton's introductory book Programming in ...
1
vote
3answers
2k views

What are the implications of P=NP? [duplicate]

Is there a list of implications of $P=NP$? Presumably, a proof of $P \ne NP$ will be by contradiction, for which a list of consequences of $P=NP$ would be useful.
1
vote
2answers
994 views

How to prove that the reversal of the concatenation of two strings is the concatenation of the reversals?

Given languages $L_1$ and $L_2$, how do we prove that $$(L_1L_2)^{\mathrm{rev}} = (L_2^{\mathrm{rev}})(L_1^{\mathrm{rev}})\,,$$ where ${}^{\mathrm{rev}}$ denotes reversal? I think using mathematical ...
1
vote
1answer
412 views

How to show that two vertices in a connected component are in the same set? (bi conditional)

Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices are in the same connected component if and only if they are in the same set. The CONNECTED-COMPONENTS algorithm is the ...
0
votes
2answers
1k views

Proving $(a+b)^* = b^*(ab^*)^*$ equationally

I am new to automata theory and have a problem in understanding equivalence of regular expressions, though I can go for the construction procedure of minimized DFAs to prove that both are equal. I ...
1
vote
0answers
124 views

Program equivalence with Structural induction

I recently attended my first lecture on structural induction and the professor stated that structural induction can be used to to prove that two programming languages are equivalent. I am new to ...
1
vote
1answer
78 views

Is this argument wrong “since DOM is special kind of RDOM, then RDOM is NP-hard”?

The domination problem $DOM$ is defined as $$ DOM = \{ \langle G,k \rangle\ | \ G \text{ has a domination of size } k, K \in \mathbb{N} \}, $$ and the rainbow domination problem $RDOM$ is defined as $$...
29
votes
2answers
25k views

How to prove greedy algorithm is correct

I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...
0
votes
1answer
61 views

When reducing from HALT, can you create a Turing machine that asks whether a simulation stops?

Lets say I am doing a reduction from $\mathrm{HALT}_{\mathrm{TM}}$ to another language $S$, in order to prove that $S$ is not decidable. For this I need to build a new Turing machine, $M'$. Can I ...
3
votes
1answer
56 views

Question regarding Karp-Lipton theorem

In the proof in wikipedia, it goes like this: Let $L \in \Pi_{2}$, so we can describe membership in $L$ as a formula: $\forall_{y}\exists_{z} V(x,y,z)=1 \iff x \in L$ (where V is polynomial ...
4
votes
1answer
55 views

How to handle an undefined case with µ-recursive functions?

How to construct my proof and generally what should I aim to get when showing a function is $\mu$-recursive? Should I transform it in some of the basic functions using the given operators? For ...
0
votes
2answers
227 views

How to prove that a language $A$ is decidable?

How to prove: A language $A$ is decidable $\Leftrightarrow$ if there is a turing machine which lists $A$ in a word length alphabetically ordering. Word length alphabetically means a sorting first ...
2
votes
3answers
973 views

Structure of a Pumping Lemma proof: contradiction or counterexample?

This site is full of Pumping Lemma questions, and I do admit I've not read them all. I've tried some proofs myself and they seem to work, but I can't find anywhere what is the (general) exact ...
0
votes
0answers
37 views

Proof of RAP-derivation sequence for a set of functional dependencies in relational databases

I'm reading David Maier's outstanding but out-of-print book on relational databases (the book,"The Theory of Relational Databases", is available online from the author's website http://web.cecs.pdx....
0
votes
2answers
1k views

Prove the halting problem is undecidable using Rice's theorem

Is it possible to prove that the Halting problem is undecidable using Rice's theorem? Here's what I've tried and failed: We want to reduce Rice's Theorem (decide if a language has the nontrivial ...
-1
votes
1answer
131 views

What do we mean when we say an edge (u,v) connects some component to other component in forest G = (V,A)

Let H = (V,E) be a connected, undirected graph. Let A be a subset of E. Let C = (W , F) be a connected component (tree) in the forest G = (V,A). Let (u,v) be an edge connecting C to some other ...
1
vote
3answers
160 views

What is wrong with this reasoning that finding the genus of a degree 3 bipartite graph is NP-complete?

Finding genus of a biparite graph is $NP$-complete and finding genus of a degree $3$ graph is $NP$-complete and so finding genus of a degree $3$ bipartite graph is $NP$-complete. Though implication ...
2
votes
0answers
129 views

Proving weak simulation

I want to prove something but I am not sure if it is the right way to do it. I have two LTS that define different semantics. A=($Q_a,Λ,\to)$, and B=$(Q_b,Λ\cup\{\beta\},\leadsto)$, where $\beta$ is ...
3
votes
1answer
91 views

How to come up the number of nodes on a given level in heaps?

CLRS asked it's readers to prove that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height $h$ in any n-element heap as an exercise. The principle of Mathematical Induction can be used to prove ...
0
votes
0answers
41 views

How would one prove that the following scheme definition is an ordered stream of integers

How would one prove that the following scheme definition is an ordered stream of integers (define integers (cons-stream 1 (add-streams ones integers)))
3
votes
1answer
341 views

Modal logic axiom S4, transitive and reflexive frame, tableaux solver

I have a difficult problem to solve which as mentioned in the title is related to modal logic axiom S4. So, here is some background knowledge that can be useful: S4 axiom is a class of transitive and ...
1
vote
1answer
823 views

Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable

$$L = \{ \langle M \rangle \mid \text{\(M\) is a Turing Machine and \(|L(M)| = 1\)} \}$$ I have to prove that this is not R.E. and not co-R.E. I know how to approach these kind of problems. For $\...
1
vote
3answers
4k views

Can I simplify log(n+1) before showing that it is in O(log n)?

Had a question about the following: $$\log (n+1) \in O(\log n)$$ Can the left side be simplified any further or do I need to just go ahead and find a c and n that hold?
0
votes
0answers
25 views

How do I prove a language is regular? [duplicate]

I've done a lot of research on this topic, but still don't feel very confident about it. Let's say the example is: For a language L over an Σ, define N(L)={w∈Σ∗: wk∈L for some k∈Σ∗}. Prove that, if L ...
3
votes
1answer
135 views

How can I check constraints on my state machine behaviour?

My background is fairly practical rather than theoretical, so this question may be a bit basic. I have a state machine with events, and events may optionally trigger action functions to be called as ...
0
votes
2answers
469 views

Big-O Justification Question

I am trying to justify the big-O order of a runtime complexity by finding a $c$ and $n_0$ that hold for it. Does the left side of the justification need to be one or higher, or can it be any value so ...
0
votes
0answers
120 views

How not to prove that P ≠ NP implies NP ≠ PSPACE

Let's define the two variants of the Travelling salesman problem: $TSP_{opt}$ : Give me the shortest tour $TSP_{dec}$ : Is there a tour of $l$ or shorter (Yes/No) Now assume $P \neq NP$: Since $...