User rb612

8 votes

1 answer

4k views

How do we know for sure that EXPTIME ≠ P?

asked Jun 1, 2016 at 6:26

6 votes

1 answer

897 views

How does (non)deterministic time relate to verifiability?

asked Jun 2, 2016 at 3:37

6 votes

1 answer

1k views

Is EXPTIME "solvable" or "checkable" in exponential time?

asked May 29, 2016 at 7:56

5 votes

3 answers

1k views

What complexity class would this version of generalized chess fall?

asked Jun 2, 2016 at 5:04

4 votes

2 answers

1k views

How are games like chess provably harder than NP?

asked Jun 3, 2016 at 4:34

3 votes

1 answer

596 views

NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?

asked Jan 11, 2018 at 8:12

2 votes

1 answer

134 views

Questions on Sipser's NP implying verifiability?

asked Apr 14, 2018 at 8:23

1 vote

1 answer

30 views

Injectivity not required for unification algorithms?

asked Mar 25, 2020 at 11:31

1 vote

0 answers

40 views

How is it possible that an equational theory be terminating?

asked Mar 28, 2020 at 12:09

1 vote

1 answer

210 views

General Intelligence Utility Function

asked Mar 28, 2017 at 2:10

1 vote

0 answers

152 views

Second-order Markov text generation?

asked Jul 2, 2017 at 5:16

0 votes

1 answer

75 views

Looping through random integers - will it halt with probability 1?

asked Nov 18, 2017 at 10:49

Stack Exchange Network

12 Questions

How do we know for sure that EXPTIME ≠ P?

How does (non)deterministic time relate to verifiability?

Is EXPTIME "solvable" or "checkable" in exponential time?

What complexity class would this version of generalized chess fall?

How are games like chess provably harder than NP?

NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?

Questions on Sipser's NP implying verifiability?

Injectivity not required for unification algorithms?

How is it possible that an equational theory be terminating?

General Intelligence Utility Function

Second-order Markov text generation?

Looping through random integers - will it halt with probability 1?