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
392 views

### How to prove this language is regular [duplicate]

Let $L$ be a regular language with alphabet $\Sigma = \{a,b,c\}$. Prove that the following language is regular: $\{w | w \in L \text{ and } w \text{ starts with } abc \}$. I wonder what proof ...
26 views

### Avoiding pumping lemma [duplicate]

Is there a way to show $\{a^nb^nc^n:n\geq0\}$ is not regular without pumping lemma?
86 views

### Is $A_{PTM}$ a BPP-complete language?

The language $A_{PTM}$ is defined as the acceptance problem on a Probabilistic Turing machine. $A_{PTM}=$ { $<M, x> | M$ on input $x$ accepts with an error probability less than or equal to 1/...
42 views

### Prove a language $A_{PTM}$ is not BPP-Complete

I am trying to prove that there are a language is not BPP-Complete. There are a couple of examples online, but they are not the best examples and are a bit complicated. I spoke with one of my computer ...
61 views

### Why does the proof that #SAT is in IP stop after m rounds?

I've been struggling to understand why the interactive proof for #SAT stops after only $m$ rounds, where $m$ is the number of variables in the formula $\phi$. I understand that two polynomials of ...
235 views

### A question about an input in a Halting Problem proof

Here is my Halting Problem proof, that largely mirrors other (non-diagonalizing) proofs that I've seen. $H(p,i)$ returns $1$ if program $p$ halts on input $i$. $H(p,i)$ returns $0$ if program $p$ ...
355 views

274 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, ...
283 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 ...
136 views