Skip to main content
4 votes

Computability- relationship between R, coRE and RE

Since $L_1$ is not computably enumerable, it has to be infinite. It follows that $L_1$ has continuumsly many sublanguages, of which only countably many are co-computably-enumerable. So we can pick $...
Arno's user avatar
  • 3,183
4 votes

Why get this P=NP? What I am doing wrong?

Both $\texttt{P}$ and $\texttt{NP}$ are subsets of the recursive function $\texttt{R}$, so by definition all $\texttt{NP}$ problems must be decidable by DTMs. But that doesn't make them equal. The ...
Knogger's user avatar
  • 1,327
2 votes

Deducing upper bound for Boolean Circuit size from well-known algorithms

A Turing machine running in time $t(n)$ can be simulated by circuits of size $O(t(n)\log t(n))$; see e.g. https://cseweb.ucsd.edu/classes/sp11/cse201A-a/ln412.pdf .
Emil Jeřábek's user avatar
2 votes

Analog computers more powerful than turing machines?

As far as anyone can tell, no, analog computers are not more powerful than Turing machines. In practice, they run into problems with errors accumulating rapidly. It's also worth pointing out that ...
D.W.'s user avatar
  • 162k
2 votes

Polynomial solutions, one less

Suppose $L = \{(G_x, Y) \mid Y$ is the maximum or minimum vertex cover of $G_x\}$. This satisfies your requirements. Now let for $G_{x_0}$, we discard $Y_a$ as the maximum vertex cover (which is all ...
codeR's user avatar
  • 1,465
1 vote

Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

I would like to present an answer that evokes the historical motivation for defining the Turing machine. You're solving mathematical problems. What kind of problems can you solve without any leap of ...
gnarrithas's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible