Raising a Hardness Result

Details Raising a Hardness Result Raising a Hardness Result

2007-08-30

arxiv.org/abs/0708.4170v1

Computer Science

Artificial Intelligence

Scientific paper

This article presents a technique for proving problems hard for classes of the polynomial hierarchy or for PSPACE. The rationale of this technique is that some problem restrictions are able to simulate existential or universal quantifiers. If this is the case, reductions from Quantified Boolean Formulae (QBF) to these restrictions can be transformed into reductions from QBFs having one more quantifier in the front. This means that a proof of hardness of a problem at level n in the polynomial hierarchy can be split into n separate proofs, which may be simpler than a proof directly showing a reduction from a class of QBFs to the considered problem.

Affiliated with

Also associated with

No associations

Rating

Raising a Hardness Result 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 Raising a Hardness Result, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Raising a Hardness Result will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-206113