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

638 questions
Filter by
Sorted by
Tagged with
42 views

### are all questions qbfs? because they are based on logic? [closed]

do all logicians on earth know that a question is a qbf? yes and they know the answer to a qbf is always yes or no? yes ok good all logicians know that solving one qbf is hard and buggy? yes but ...
63 views

### Validity of proof by contradiction

I had a doubt in the proof by contradiction technique. Under this technique, we assume the negation of what we want to prove as true, then show that assuming so generates a contradiction. Since a ...
23 views

### Is it common to prove that some code is the simplest way to achieve something?

I have a simple program which achieves a certain functionality. I’m interested to know if it can be proven that the steps in the program are the theoretically simplest way to achieve those results. Is ...
28 views

### Suppose f(n) is O(h(n)) and g(n) is O(h(n)). Is f(n) * g(n) is O(h(n) * h(n))

I understand this should be a relatively easy proof, but I can't seem to understand how to do it. I know that, by Big O definition: There exists some value C1 where f(n) <= C1 * h(n) for all N >=...
31 views

### NP-hardness proof of an optimization problem with real values and real input in the decision problem

Question - Let's suppose we have an optimization problem $\mathcal{P}$ with a real-valued measure function and the decision version of the optimization problem $\mathcal{P}_D$ (please see definitions ...
78 views

### NP-hardness proof of an optimization problem with real values and rational input in the decision problem

I'm studying complexity theory and I have the below question regarding $NP$-hardness proofs of optimization problems with real values. Any reference is much appreciated. For the question, take the ...
59 views

### How to prove that the problem $\text{"If$L$is a context-free language, then, is$\overline{L}$also context-free?"}$ is undecidable?

Lately I came across a problem: $\text{"If$L$is a context-free language, then, is$\overline{L}$also context-free?"}$ And I need to comment on its decidability. Now I know that context free ...
106 views

### Invariant vs Assertion vs lemma

I am reading Distributed Algorithms by Nancy Lynch. I have come across lemmas, assertions and invariants, but I do not understand the difference between them. I think lemma means an intermediate ...
41 views

### Mutual Friends in a Network?

I always seem to have trouble finding a formal way to analyze this (be through proofs or whatever). The problem statement is as such: If A and B are friends, and B and C are friends, then A and C are ...
28 views

### M does not accept [M] | 'Correction' of proof possible?

The language $D=\{[M]|M([M])=0\}$ is not decidable because of the following argument: Suppose there was a $TM \space M_D$ that decides $D$. Then if we gave $M_D \space [M]$, there would be two ...
38 views

### How can I use induction for proving termination of a string rewriting system?

If we have a string rewriting system within the alphabet $\{X,Y\}^*$ and the rule $XY\to YX$. How can we prove by induction that on every string input the system terminates?
110 views

### Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less

I am trying to prove that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ such that a DFA accepting $A_k$ has $k$ states but no less. I thought about proving this in two ways: ...
46 views

### How to prove NP-hardness of a Hamiltonian Path problem by reducing longest-path problem?

I know how to prove longest-path problem by reducing Hamiltonian Path problem. Here I want to prove NP-hardness of a Hamiltonion Path problem by reducing longest-path problem. (pretend we know longest-...
35 views

### Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?"

Do two halting Turing machines accept the same language? Proof that it is undecidable(credit to another user on this website: "Tom van der Zanden"): Let M be an arbitrary Turing machine. Let ...
### Proving that $f(n) \not\in O(n)$ given that $f(n) \in \Theta(n^2)$ and the formal definitions of Big-Oh and Theta
So far I've understood that because of the definition of $\Theta$, we have $c_1n^2 \le f(n) \le c_2n^2$. I'm not sure how to proceed from there.