Arno's user avatar
Arno's user avatar
Arno's user avatar
Arno
  • Member for 6 years, 4 months
  • Last seen this week
19 votes

Probabilistic methods for undecidable problem

18 votes
Accepted

Detecting if three Turing Machines halt given a magic oracle that is only used twice

14 votes
Accepted

Do any decision problems exist outside NP and NP-Hard?

8 votes
Accepted

Assuming P != NP, what is the cardinality of the set of NP-Hard languages?

8 votes
Accepted

What is the "continuity" as a term in computable analysis?

8 votes
Accepted

Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL

7 votes
Accepted

Given A to C, and B to C with known complexities, what can be said about A to B?

6 votes

Can a computer determine whether a mathematical statement is true or not?

5 votes
Accepted

Does the term "continuity" have a different meaning in maths and in CS?

5 votes
Accepted

CFG for the language {ω ∈ {a, b}*| in every prefix of ω, the number of a’s is greater than or equal to number of b’s}

5 votes
Accepted

Proof that $NP \cap coNP = P$

4 votes
Accepted

Polynomial Hierarchy - the difference between $\Pi$ and $\Sigma$

4 votes

is there a constructive proof of the existence of a language which isn't recursive (without invoking infinities)?

4 votes

Is it possible that Co-NP = P but NP != P

4 votes
Accepted

Does godel's incompleteness theorem still hold if we have a TM that can do an infinity amount of computations?

4 votes

Why doesn't Godel's Second Incompleteness Theorem rule out a formalizable proof of P!=NP?

4 votes
Accepted

Proving FPT is strictly contained in XP

4 votes
Accepted

How does one define transcendental numbers (such as Pi) in theory of general recursive functions

3 votes

can you write a halting decider that is only wrong about itself by avoiding diagonalization?

3 votes

Is there a TM that halts iff P = NP?

3 votes
Accepted

If a computer can demonstrate singleton sets are closed, is the space Hausdorff?

3 votes

Cardinality of the set of algorithms

3 votes

Is there any other computation theory besides the one in automata theory?

3 votes
Accepted

Is Rice-Shapiro theorem bidirectional?

3 votes
Accepted

Is the set of language decidable by some Turing machine computing in some given computable time bound decidable

3 votes
Accepted

Why is this language Turing recognizable and not not-Turing recognizable

3 votes

What is wrong with the following $P$ problem?

2 votes

Analogue of the topology-computability correspondence for computational complexity

2 votes
Accepted

Proof for Turing Machines being able to simulate any algorithm in the same time complexity

2 votes

Error in proof of decidability