Travis Service

Reputation

912

Next privilege

1,000 Rep.

See votes

Yearling

0/1

0 posts edited

0 helpful flags

69 votes cast

36	Easy decision problem, hard search problem
18	Algorithms for set packing
10	Lattice problems
6	Computable function $f = \Theta(g)$ with $g$ uncomputable

This user has no recent positive reputation changes

View more →

21	Finding twin vertices in graphs
15	Do the undecidable attributes of P pose an obstruction to deciding P versus NP? (answer: maybe)
8	Global properties of hereditary classes?

This user has not participated in any tags

68	Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)
20	Positive topological ordering, take 3
13	An extension of Chernoff bound