User blademan9999

1

vote

1

answer

50

views

What would be the practical consequences of ZPP=exptime

complexity-theory time-complexity

Apr 3 at 23:43 Kyle Jones 7,270

0

votes

1

answer

57

views

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

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

Mar 5 at 1:00 Community♦ 1

1

vote

0

answers

19

views

Is QMA known to contain Co-NP?

np complexity-classes quantum-computing

Jul 19 at 5:25 blademan9999 250

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

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

0

votes

0

answers

14

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

99

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

2

votes

1

answer

119

views

Is P/poly known to be in RE?

complexity-theory time-complexity complexity-classes

Jun 11 at 21:42 jmite 28.3k

0

votes

0

answers

26

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,270

-1

votes

1

answer

45

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

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

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

166

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 648

0

votes

0

answers

39

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

22

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

vote

2

answers

139

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 22.3k

1

vote

0

answers

80

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

2

votes

0

answers

32

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

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

21 Questions

What would be the practical consequences of ZPP=exptime

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

Is QMA known to contain Co-NP?

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

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

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?

Is P/poly known to be in RE?

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

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]

Is $NC_1$ vs PP still an open problem?

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?

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?

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