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

520 questions
Filter by
Sorted by
Tagged with
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.
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 ...
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 ...
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, ...
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 ...
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$ ...
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 ...
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 ...
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$ ...
497 views

584 views

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