User Mike Battaglia

13 votes

1 answer

549 views

Random Access Machines with only addition, multiplication, equality

asked Jun 14, 2017 at 21:43

10 votes

2 answers

529 views

Do there exist "O(1)-complete" problems?

asked Jun 14, 2017 at 20:09

7 votes

1 answer

2k views

In a bloom filter, why does the optimal number of hashes increase with the number of bits in the filter?

asked Jun 1, 2018 at 20:29

6 votes

1 answer

1k views

Do "Type-2" Turing machines with infinite length inputs have more computational power?

asked May 22, 2018 at 5:24

5 votes

1 answer

317 views

How hard is random SAT?

asked Sep 30, 2021 at 20:51

4 votes

1 answer

248 views

How many "compressible" strings are there?

asked Nov 18, 2019 at 20:36

4 votes

0 answers

84 views

Real RAMs with "reasonable" operations

asked Jul 2, 2017 at 16:57

3 votes

1 answer

86 views

"Insensitive" CNF/DNF SAT always satisfying same number of clauses

asked Jun 18, 2017 at 22:39

3 votes

1 answer

484 views

Infinite Boolean circuits as a model of computation

asked Sep 20, 2017 at 6:06

3 votes

1 answer

31 views

Variance of MAXSAT clause satisfiability

asked Nov 13, 2018 at 23:51

3 votes

1 answer

43 views

General structure of solutions to 3-SAT circuits

asked Nov 16, 2018 at 21:05

2 votes

2 answers

826 views

Proving that a sentence in first-order logic is not valid

asked Sep 22, 2017 at 1:03

2 votes

1 answer

180 views

The "complexity" of the Turing machine state specification

asked May 14, 2018 at 16:52

2 votes

1 answer

391 views

Turing machine with a countably infinite alphabet

asked May 17, 2017 at 23:59

2 votes

1 answer

2k views

Intuition behind straight-line programs

asked Jun 2, 2017 at 23:19

2 votes

1 answer

44 views

Looking for all "valid" combinations taken from a set of things, where subsets of "valid" things are always "valid"

asked Jul 13 at 23:32

1 vote

2 answers

51 views

Estimating the number of elements shared in two sets using a random sample

asked Jul 24 at 5:52

1 vote

0 answers

40 views

Networks and data flow - graph algorithms for propagating updates from nodes correctly

asked May 15 at 23:57

1 vote

0 answers

18 views

How difficult are lattice algorithms for low-dimensional lattices?

asked Jun 13 at 23:35

1 vote

0 answers

488 views

Does FNP-complete = NP-complete?

asked Oct 9, 2013 at 0:41

1 vote

1 answer

305 views

The sorting problem for partially ordered sets

asked Sep 7, 2017 at 4:11

1 vote

1 answer

284 views

NTM's and the halting problem

asked Sep 20, 2017 at 5:13

1 vote

1 answer

208 views

Complexity of 1-in-3 SAT variant with restrictions on "unique" variables per clause

asked Nov 29, 2017 at 2:48

1 vote

1 answer

876 views

NP-completeness and reduction of MAX-XOR-SAT and MAX-2-XOR-SAT [duplicate]

asked Nov 17, 2018 at 16:36

1 vote

1 answer

163 views

Lack of time hierarchy theorem for probabilistic machines

asked Jun 5, 2018 at 23:43

Stack Exchange Network

25 Questions

Random Access Machines with only addition, multiplication, equality

Do there exist "O(1)-complete" problems?

In a bloom filter, why does the optimal number of hashes increase with the number of bits in the filter?

Do "Type-2" Turing machines with infinite length inputs have more computational power?

How hard is random SAT?

How many "compressible" strings are there?

Real RAMs with "reasonable" operations

"Insensitive" CNF/DNF SAT always satisfying same number of clauses

Infinite Boolean circuits as a model of computation

Variance of MAXSAT clause satisfiability

General structure of solutions to 3-SAT circuits

Proving that a sentence in first-order logic is not valid

The "complexity" of the Turing machine state specification

Turing machine with a countably infinite alphabet

Intuition behind straight-line programs

Looking for all "valid" combinations taken from a set of things, where subsets of "valid" things are always "valid"

Estimating the number of elements shared in two sets using a random sample

Networks and data flow - graph algorithms for propagating updates from nodes correctly

How difficult are lattice algorithms for low-dimensional lattices?

Does FNP-complete = NP-complete?

The sorting problem for partially ordered sets

NTM's and the halting problem

Complexity of 1-in-3 SAT variant with restrictions on "unique" variables per clause

NP-completeness and reduction of MAX-XOR-SAT and MAX-2-XOR-SAT [duplicate]

Lack of time hierarchy theorem for probabilistic machines