We’re rewarding the question askers & reputations are being recalculated! Read more.

# 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
390 views

### Proving correctness of an iterative Fibonacci algorithm

One of the questions in the problem sets that I'm struggling in is this specific number that asks me to prove an iterative Fibonacci algorithm. The algorithm is written below: ...
629 views

### Prove that Big-O is transitive by relation. What does it mean by 'by relation'?

Prove $f(n) = O(g(n))$ and $g(n) = O(h(n))$, then $f(n) = O(h(n))$. The question is Prove that Big-O is transitive by relation. What does it mean by ...
196 views

34 views

### What's the polynomial involved in the PCP theorem?

Statements of the PCP theorem always speak of a proof of length $poly(n)$. But what polynomial is that exactly? Could you actually construct the PCP for some mathematical fact in real life?
74 views

### How to prove that a stack is equivalent to a queue with reversed inputs

Say I push the values 1,2,3,4 onto a stack. Then popping them, they will come back in the order 4,3,2,1. If I push the values 1,2,3,4 onto a queue then removing from a queue results in 1,2,3,4. ...
94 views

### How to prove for string of triplets that it is a Regular Language? [duplicate]

Let Σ2 = {0, 1}, and define Σ = Σ23. Informally, Σ* is the set of triples of the form (a, b, c) where a, b, c are single binary digits. Consider a string s ∈ Σ* : it is a sequence of such triples. ...
101 views

### Language of CFG: $S \to aS | aSbS | \varepsilon$

I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\{ w \in \{a,b\}^*: \text{every prefix of$w$has at least as many$a$'s as$b$'s} \}$.I ...
51 views

### Prove $T$ is a BST iff for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$

Let $T$ be a complete binary tree. Prove that $T$ is a binary search tree if and only if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child ...
I am currently working on a seminar on $\mathbf{P \stackrel{?}{=} NP}$ and one of the points I want to adress is the Relativization barrier. However, it is hard to find a concrete definition of a "...
I need to prove that TAUT is coNP-complete. I showed that $\text{TAUT} \in \text{coNP}$ by reducing $\text{SAT}$ to $\overline{\text{TAUT}}$. However, I cannot figure out how to prove that every ...