User Thomas Klimpel

23 votes

Accepted

Is anyone aware of a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm?

answered Aug 16, 2015 at 9:37

19 votes

Turing Machine restrictions that render halting decidable

answered May 12, 2016 at 22:43

16 votes

Accepted

What evidence is there that Graph Isomorphism is not in $P$?

answered Aug 3, 2015 at 8:37

13 votes

Accepted

Does P/poly $\neq$ NP/poly have any interesting implications?

answered Jun 28, 2015 at 12:57

12 votes

Accepted

Is there an algorithm that finds the forbidden minors?

answered Nov 3, 2018 at 16:58

10 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

answered Apr 20, 2016 at 8:36

9 votes

Accepted

Is the finite inverse semigroup isomorphism problem GI-complete?

answered Jul 16, 2015 at 0:55

6 votes

Accepted

doubt about two minesweeper gadgets

answered May 31, 2015 at 12:24

5 votes

Reasons to believe $P \ne NP \cap coNP$ (or not)

answered Jan 19, 2014 at 16:44

5 votes

Accepted

Idea for a white-box PIT deterministic algorithm in polynomial time

answered Jan 4, 2015 at 12:29

5 votes

Why is the circuit class AC0 unavoidable?

answered Mar 25, 2018 at 16:28

5 votes

Problems Between P and NPC

answered Jun 8, 2018 at 7:42

5 votes

Polynomial-time algorithms with huge exponent/constant

answered Jan 22, 2018 at 0:44

4 votes

Accepted

what can be said about complexity of "typical" supercomputing programs/ applications? any NP hard?

answered Aug 2, 2015 at 9:35

4 votes

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

answered Nov 5, 2019 at 11:56

3 votes

The unreasonable power of non-uniformity

answered May 2, 2014 at 12:07

3 votes

Accepted

Multiplication of circulant matrices with a diagonal matrix

answered Dec 1, 2014 at 20:34

3 votes

Alternative proofs of Schwartz–Zippel lemma

answered Mar 10, 2015 at 9:01

3 votes

Accepted

Closure properties of $L$ (DLOGSPACE)?

answered Jul 29, 2017 at 22:23

3 votes

List of quantum-inspired algorithms

answered Feb 10, 2019 at 19:11

2 votes

Is ALogTime != PH hard to prove (and unknown)?

answered Aug 12, 2017 at 20:04

2 votes

Is true randomness and the physical Church-Turing thesis incompatible?

answered Mar 23, 2018 at 3:50

2 votes

Accepted

Quasi-polynomial time algorithm for permutation group isomorphism

answered Feb 11, 2016 at 8:32

2 votes

Massive online collaboration for solving open problem in theoretical computer science

answered Sep 13, 2015 at 16:33

2 votes

Accepted

Can message passing help in GI related problems?

answered Apr 9, 2017 at 13:38

2 votes

Accepted

Relativized world where $L^A=NP^A$

answered May 21, 2015 at 22:38

2 votes

What is the difference between non-determinism and randomness?

answered Jan 25, 2015 at 15:42

2 votes

Is there a theory that combines category theory/abstract algebra and computational complexity?

answered Jul 21, 2015 at 7:29

2 votes

Accepted

When is it hard to invert a sparse matrix?

answered Sep 22, 2020 at 22:43

1 vote

Would a proof that the traveling salesman algorithm can't be encoded on LAL also prove P!=NP?

answered Jul 29, 2015 at 9:00

Stack Exchange Network

37 Answers

Is anyone aware of a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm?

Turing Machine restrictions that render halting decidable

What evidence is there that Graph Isomorphism is not in $P$?

Does P/poly $\neq$ NP/poly have any interesting implications?

Is there an algorithm that finds the forbidden minors?

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Is the finite inverse semigroup isomorphism problem GI-complete?

doubt about two minesweeper gadgets

Reasons to believe $P \ne NP \cap coNP$ (or not)

Idea for a white-box PIT deterministic algorithm in polynomial time

Why is the circuit class AC0 unavoidable?

Problems Between P and NPC

Polynomial-time algorithms with huge exponent/constant

what can be said about complexity of "typical" supercomputing programs/ applications? any NP hard?

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

The unreasonable power of non-uniformity

Multiplication of circulant matrices with a diagonal matrix

Alternative proofs of Schwartz–Zippel lemma

Closure properties of $L$ (DLOGSPACE)?

List of quantum-inspired algorithms

Is ALogTime != PH hard to prove (and unknown)?

Is true randomness and the physical Church-Turing thesis incompatible?

Quasi-polynomial time algorithm for permutation group isomorphism

Massive online collaboration for solving open problem in theoretical computer science

Can message passing help in GI related problems?

Relativized world where $L^A=NP^A$

What is the difference between non-determinism and randomness?

Is there a theory that combines category theory/abstract algebra and computational complexity?

When is it hard to invert a sparse matrix?

Would a proof that the traveling salesman algorithm can't be encoded on LAL also prove P!=NP?