User blademan9999

2

votes

1

answer

118

views

Is P/poly known to be in RE?

Jun 11 at 21:42 jmite 28.2k

2

votes

0

answers

31

views

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

complexity-theory time-complexity complexity-classes polynomial-time

Jun 7 at 18:30 blademan9999 250

1

vote

0

answers

18

views

Is QMA known to contain Co-NP?

np complexity-classes quantum-computing

Jul 19 at 5:25 blademan9999 250

1

vote

0

answers

17

views

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

complexity-theory complexity-classes np-intermediate

Jun 19 at 16:33 blademan9999 250

1

vote

0

answers

25

views

Is $NC_1$ vs PP still an open problem?

complexity-theory complexity-classes

Jun 10 at 6:36 blademan9999 250

1

vote

2

answers

112

views

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

formal-languages programming-languages halting-problem loops

Jun 7 at 22:29 gnasher729 21.5k

1

vote

0

answers

79

views

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

complexity-theory time-complexity complexity-classes

Jun 7 at 18:31 blademan9999 250

1

vote

1

answer

31

views

What would be the practical consequences of ZPP=exptime

complexity-theory time-complexity

Jun 6 at 17:47 Community♦ 1

0

votes

1

answer

49

views

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

complexity-theory time-complexity complexity-classes oracle-machines

Nov 5 at 0:05 Community♦ 1

0

votes

0

answers

14

views

Can you give an example of a problem in $EXP^{RE}$ but not In $P^{RE}$

complexity-theory complexity-classes halting-problem oracle-machines

Jun 24 at 1:34 blademan9999 250

0

votes

0

answers

10

views

What is $S2-EXP•P^{NP}$?

complexity-theory complexity-classes

Jun 19 at 15:17 blademan9999 250

0

votes

0

answers

19

views

Is this Correct, the existence of cryptography requires $UP \cap Co-UP \not\subseteq BPP$

complexity-theory complexity-classes cryptography encryption

Jun 15 at 9:55 blademan9999 250

0

votes

0

answers

41

views

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

complexity-theory complexity-classes one-way-functions

Jun 15 at 5:04 blademan9999 250

0

votes

1

answer

91

views

What complexity class is the TSP problem?

complexity-theory np-complete np-hard complexity-classes traveling-salesman

Jun 14 at 15:07 salcc 69

0

votes

0

answers

25

views

Assuming the Exponential Time Hypothesis is true, what's the fastest possible algorithm that can be produced for NP-complete problems? [duplicate]

complexity-theory time-complexity np-complete complexity-classes 3-sat

Jun 10 at 14:42 Kyle Jones 7,125

0

votes

0

answers

19

views

What decision problems are their that are outside of elementary but still decidable

complexity-theory time-complexity decision-problem complexity-classes

Jun 10 at 2:16 blademan9999 250

0

votes

1

answer

124

views

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

complexity-theory turing-machines time-complexity complexity-classes halting-problem

Jun 9 at 23:10 Glorfindel 644

0

votes

0

answers

32

views

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

turing-machines pushdown-automata halting-problem

Jun 9 at 17:32 blademan9999 250

1

0

votes

0

answers

26

views

What's the class of problems solvable in polynomial time with an exponential number of processors?

complexity-theory time-complexity complexity-classes polynomial-time

Jun 8 at 15:05 blademan9999 250

0

votes

0

answers

21

views

What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat?

complexity-theory time-complexity np-complete complexity-classes 3-sat

Jun 8 at 12:47 blademan9999 250

-1

votes

1

answer

44

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]

turing-machines halting-problem

Jun 10 at 9:22 frabala 711

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

21 Questions

Is P/poly known to be in RE?

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

Is QMA known to contain Co-NP?

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

Is $NC_1$ vs PP still an open problem?

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

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

What would be the practical consequences of ZPP=exptime

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

Can you give an example of a problem in $EXP^{RE}$ but not In $P^{RE}$

What is $S2-EXP•P^{NP}$?

Is this Correct, the existence of cryptography requires $UP \cap Co-UP \not\subseteq BPP$

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

What complexity class is the TSP problem?

Assuming the Exponential Time Hypothesis is true, what's the fastest possible algorithm that can be produced for NP-complete problems? [duplicate]

What decision problems are their that are outside of elementary but still decidable

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

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

What's the class of problems solvable in polynomial time with an exponential number of processors?

What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat?

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]