1
vote
1answer
64 views

What's wrong with this argument for $NP \ne EXP$?

Let $\{M_i\}$ be any enumeration of all Turing machines in which each machine appears an infinite number of times. Consider the language $D = \{i \, | \, M_i(i) \text{ does not accept within ...
6
votes
2answers
1k views

Every language is regular?

Could anyone tell me the error in my reasoning: The set of strings of a given alphabet is a countable set. Every string can be determined by a regular language. The union of two regular languages is ...
2
votes
3answers
460 views

Fake Proof that $\mathrm{NP}^\mathrm{NP} = \mathrm{NP}$

I found this faulty proof of $$ \newcommand{\NP}{\mathrm{NP}} \NP = \NP^{\NP}, $$ where the tricky part is to proof that $ \NP ^{\NP} \subseteq \NP$, and this is how it is realized: Take $\NP^\NP$ ...
6
votes
2answers
369 views

Faulty proof of polynomial hierarchy first level collapse?

I am an undergraduate of CS and I participate in TCS.SE. I am having trouble finding the error in a proof about the polynomial hierarchy collapsing to the first level ($NP = coNP$). I believe the ...