blademan9999's user avatar
blademan9999's user avatar
blademan9999's user avatar
blademan9999
  • Member for 3 years, 10 months
  • Last seen more than a month ago
  • Hong Kong
3 votes
2 answers
314 views

Do there exist coding languages where the halting problem is solvable but not trivial

3 votes
1 answer
167 views

Is QMA known to contain Co-NP?

3 votes
0 answers
75 views

What's the fastest known non-galactic algorithm for matrix multiplication of large matrices

2 votes
0 answers
70 views

Are there problems that are known to be in ZPP but not in p

2 votes
1 answer
161 views

What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to

2 votes
1 answer
219 views

Is P/poly known to be in RE?

1 vote
2 answers
1k views

What's the complexity class of determing the halting problem of a finite memory Turing machine?

1 vote
0 answers
32 views

Is $NC_1$ vs PP still an open problem?

1 vote
0 answers
99 views

What are some of the most ridiculous claims in computer science that we haven't disproved?

1 vote
0 answers
32 views

Are there any "natural problems" which are known to be NPI under weak assumptions

0 votes
1 answer
343 views

What complexity class is the TSP problem?

0 votes
0 answers
50 views

What complexity class results would be implied by a proof of the existence of one way functions

0 votes
0 answers
169 views

Can a pushdown automaton solve the halting problem for another Pushdown automaton?

0 votes
1 answer
187 views

What would be the practical consequences of ZPP=exptime

-1 votes
1 answer
64 views

Is it possible to construct a Turing Submachine such that a regular turing machine can decide whether the TSM halts but the TSM cannot [closed]