History of Sharp-P

	Revision 4 . . (edit) December 6, 2001 6:57 am by (logged).202.117.xxx
	Revision 3 . . (edit) August 25, 2001 9:56 am by LC
	Revision 1 . . August 25, 2001 9:34 am by LC

---

Difference (from prior major revision) (minor diff, author diff)

Changed: 4c4

* Are there any solutions that satisfy this these constraints?

* Are there any solutions that satisfy certain constraints?

Changed: 6,8c6,8

* Are there any subsets of a list of integers that add up to zero? * Are there any tours in a [Traveling Salesman Problem]? of length less than 100? * Are there any variable assignments that satisfy this DNF formula?

* Are there any subsets of a list of integers that add up to zero? ([subset sum problem]?) * Are there any [Hamiltonian cycle]?s in a given graph with cost less than 100? (traveling salesman problem) * Are there any variable assignments that satisfy a given DNF? formula? ([satisfiability problem]?)

Changed: 11,12c11,12

* How many tours in a [Traveling Salesman Problem]? have length less than 100? * How many variable assignments satisfy this DNF formula?

* How many Hamiltonian cycles in a given graph have cost less than 100? * How many variable assignments satisfy a given DNF formula?

Changed: 14c14

More formally, a problem is in #P if there is a nondeterministic, polynomial-time Turing machine that, for each instance I of the problem, has a number of accepting computations that is exactly equal to the number of distinct solutions to instance I.

More formally, a problem is in #P if there is a nondeterministic, polynomial-time Turing machine that, for each instance I of the problem, has a number of accepting computations that is exactly equal to the number of distinct solutions for instance I.