user avatar
user avatar
user avatar
Kyle Jones
  • Member for 10 years, 5 months
  • Last seen this week
  • Seattle, WA
213 votes
32 answers
52k views

Why is writing down mathematical proofs more fault-proof than writing computer code?

  • 3,314
177 votes
13 answers
60k views

Why, really, is the Halting Problem so important?

  • 2,477
56 votes
14 answers
18k views

Is C actually Turing-complete?

  • 1,282
46 votes
6 answers
6k views

Dealing with intractability: NP-complete problems

  • 561
40 votes
6 answers
17k views

Sorting functions by asymptotic growth

  • 609
40 votes
2 answers
11k views

Why do we believe that PSPACE ≠ EXPTIME?

  • 403
37 votes
1 answer
2k views

Is it NP-hard to fill up bins with minimum moves?

  • 3,023
36 votes
6 answers
73k views

Can a public key be used to decrypt a message encrypted by the corresponding private key?

  • 1
34 votes
3 answers
3k views

Why is Relativization a barrier?

  • 599
28 votes
1 answer
724 views

Subset sum problem with many divisibility conditions

  • 3,023
25 votes
4 answers
3k views

How to fool the plot inspection heuristic?

  • 71k
24 votes
2 answers
2k views

Is Logical Min-Cut NP-Complete?

  • 391
24 votes
3 answers
2k views

Is there a sometimes-efficient algorithm to solve #SAT?

  • 1,517
20 votes
4 answers
1k views

Why is it important for functions to be anonymous in lambda calculus?

19 votes
1 answer
3k views

When to use SAT vs Constraint Satisfaction?

  • 143k
18 votes
1 answer
976 views

Are 'zero-one' jigsaw puzzles NP-complete?

18 votes
5 answers
7k views

Why is a quantum computer not capable of solving more problems than a classical computer? [duplicate]

18 votes
7 answers
5k views

Would proving P≠NP be harder than proving P=NP?

  • 457
16 votes
8 answers
26k views

What problems of procedural programming does OOP solve in practice?

  • 261
15 votes
1 answer
3k views

Are "Flow Free" puzzles NP-hard?

13 votes
1 answer
12k views

Reachable state space of an 8-puzzle

  • 253
11 votes
1 answer
813 views

Can top SAT-solvers factor easy numbers?

10 votes
2 answers
2k views

NP-Completeness of a Graph Coloring Problem

  • 541
10 votes
2 answers
675 views

Would $\sf RP = NP$ imply $\sf NP = coNP$?

  • 737
10 votes
2 answers
3k views

What is wrong with this simple proof of P=NP?

8 votes
2 answers
1k views

How can I find minimum number required to add to sequence such that their xor becomes zero

8 votes
1 answer
311 views

How much can we reduce the number of clauses by converting from $k$-SAT to $(k+m)$-SAT?

7 votes
0 answers
148 views

Any Natural Problems shown Easy by Reduction to Horn SAT?

7 votes
0 answers
56 views

P=NP turns 50. 1971 STOC conference

7 votes
3 answers
1k views

What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time?

  • 1,189