user avatar
user avatar
user avatar
Mike Battaglia
  • Member for 8 years, 7 months
  • Last seen more than a week ago
13 votes
1 answer
485 views

Random Access Machines with only addition, multiplication, equality

9 votes
2 answers
486 views

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

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?

6 votes
1 answer
1k views

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

4 votes
0 answers
73 views

Real RAMs with "reasonable" operations

3 votes
1 answer
67 views

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

3 votes
1 answer
410 views

Infinite Boolean circuits as a model of computation

3 votes
1 answer
31 views

Variance of MAXSAT clause satisfiability

3 votes
1 answer
31 views

General structure of solutions to 3-SAT circuits

3 votes
1 answer
143 views

How many "compressible" strings are there?

3 votes
1 answer
97 views

How hard is random SAT?

2 votes
2 answers
571 views

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

2 votes
1 answer
104 views

The "complexity" of the Turing machine state specification

2 votes
1 answer
342 views

Turing machine with a countably infinite alphabet

2 votes
1 answer
1k views

Intuition behind straight-line programs

1 vote
0 answers
413 views

Does FNP-complete = NP-complete?

1 vote
1 answer
280 views

The sorting problem for partially ordered sets

1 vote
1 answer
213 views

NTM's and the halting problem

1 vote
1 answer
166 views

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

1 vote
1 answer
436 views

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

1 vote
1 answer
122 views

Lack of time hierarchy theorem for probabilistic machines