Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Function problem
Résumé
In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the output is not simply 'yes' or 'no'.
A functional problem is defined by a relation over strings of an arbitrary alphabet :
An algorithm solves if for every input such that there exists a satisfying , the algorithm produces one such , and if there are no such , it rejects.
A promise function problem is allowed to do anything (thus may not terminate) if no such exists.
A well-known function problem is given by the Functional Boolean Satisfiability Problem, FSAT for short. The problem, which is closely related to the SAT decision problem, can be formulated as follows:
Given a boolean formula with variables , find an assignment such that evaluates to or decide that no such assignment exists.
In this case the relation is given by tuples of suitably encoded boolean formulas and satisfying assignments.
While a SAT algorithm, fed with a formula , only needs to return "unsatisfiable" or "satisfiable", an FSAT algorithm needs to return some satisfying assignment in the latter case.
Other notable examples include the travelling salesman problem, which asks for the route taken by the salesman, and the integer factorization problem, which asks for the list of factors.
Consider an arbitrary decision problem in the class NP. By the definition of NP, each problem instance that is answered 'yes' has a polynomial-size certificate which serves as a proof for the 'yes' answer. Thus, the set of these tuples forms a relation, representing the function problem "given in , find a certificate for ". This function problem is called the function variant of ; it belongs to the class FNP.
FNP can be thought of as the function class analogue of NP, in that solutions of FNP problems can be efficiently (i.e., in polynomial time in terms of the length of the input) verified, but not necessarily efficiently found.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.