User Dan Brumleve

Dan Brumleve

Member for 11 years, 1 month
Last seen more than 3 years ago

math.stackexchange.com/users/…
Champaign, IL

8 Bookmarks

Score Activity Newest Views Added

38 votes

3 answers

6k views

Extended Church-Turing Thesis

Aaron Sterling

6,954

asked Jul 27, 2011 at 16:06

31 votes

6 answers

2k views

Is there a natural problem on the naturals that is NP-complete?

cc.complexity-theory np-hardness nt.number-theory combinatorial-game-theory

domotorp

13.5k

asked Oct 30, 2012 at 15:19

28 votes

2 answers

1k views

Can we not output the Kolmogorov complexity?

cc.complexity-theory kolmogorov-complexity universal-computation universal-turing-machines

domotorp

13.5k

asked Apr 26, 2015 at 11:37

18 votes

2 answers

521 views

Is it possible to encrypt a CNF?

cc.complexity-theory cr.crypto-security one-way-function cryptojacking

domotorp

13.5k

asked Dec 29, 2017 at 8:17

13 votes

2 answers

730 views

Reference for Levin's optimal factoring algorithm ?

ds.algorithms reference-request factoring

Christopher Monsanto

1,032

asked Apr 28, 2011 at 4:40

12 votes

1 answer

420 views

Which complexity class does this number theory problem belong to?

ds.algorithms complexity-classes reductions nt.number-theory np-complete

user34945

asked Aug 13, 2015 at 13:21

10 votes

4 answers

626 views

Is there a notion of computability on sets other than the natural numbers?

computability

Tom Ellis

asked Dec 1, 2017 at 15:22

5 votes

3 answers

481 views

Natural NP-complete problems with high density?

cc.complexity-theory ds.algorithms complexity-classes np

Andras Farago

10.7k

asked Nov 19, 2015 at 18:14

Stack Exchange Network

current community

your communities

more stack exchange communities

8 Bookmarks

Extended Church-Turing Thesis

Is there a natural problem on the naturals that is NP-complete?

Can we not output the Kolmogorov complexity?

Is it possible to encrypt a CNF?

Reference for Levin's optimal factoring algorithm ?

Which complexity class does this number theory problem belong to?

Is there a notion of computability on sets other than the natural numbers?

Natural NP-complete problems with high density?