The Consequences of Eliminating NP Solutions

Details The Consequences of Eliminating NP Solutions The Consequences of Eliminating NP Solutions

2006-06-02

arxiv.org/abs/cs/0606009v4

Computer Science

Computational Complexity

Scientific paper

Given a function based on the computation of an NP machine, can one in general eliminate some solutions? That is, can one in general decrease the ambiguity? This simple question remains, even after extensive study by many researchers over many years, mostly unanswered. However, complexity-theoretic consequences and enabling conditions are known. In this tutorial-style article we look at some of those, focusing on the most natural framings: reducing the number of solutions of NP functions, refining the solutions of NP functions, and subtracting from or otherwise shrinking #P functions. We will see how small advice strings are important here, but we also will see how increasing advice size to achieve robustness is central to the proof of a key ambiguity-reduction result for NP functions.

Affiliated with

Also associated with

No associations

Rating

The Consequences of Eliminating NP Solutions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Consequences of Eliminating NP Solutions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Consequences of Eliminating NP Solutions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-633276