Questions tagged [tfnp]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
73 views

If a solution to Partition is known to exist, can it be found in polynomial time?

In the Partition problem, there is a set of integers, and the goal is to decide whether it can be partitioned into two sets of equal sum. This problem is known to be NP-complete. Suppose we are given ...