# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Function problem

In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO.

Notable examples include the traveling salesman problem which asks for the route taken by the salesman, and the integer factorization problem, which asks for the list of factors.

Function problems are more awkward to study than decision problems because they don't have an obvious analogue in terms of languages, and because the notion of reduction between problems is more subtle as you have to transform the output as well as the input.

Function problems can be sorted into complexity classes in the same way as decision problems, for example FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time, and FNP is the set of function problems which can be solved by a non-deterministic Turing machine in polynomial time.

For all function problems there is an analogous decision problem such that the function problem can be solved by polynomial-time Turing reduction to that decision problem. For example, the decision problem analogue to the traveling salesman problem is this:

Given a weighted directed graph and an integer K, is there a Hamilton path with total weight less than or equal to K?

Given a solution to this problem, we can solve the traveling salesman problem as follows. Let n by the number of edges and wi be the weight of edge i. First rescale and perturb the weights of the edges by assigning to edge i the new weight w'i = n2wi + i. This doesn't change the shortest Hamilton path, but makes sure that it is unique. Now add the weights of all edges to get a total weight M. Find the weight of the shortest Hamilton path by binary search: is there a Hamilton path with weight < M / 2; is there a path with weight < M / 4 etc. Then having found the weight W of the shortest Hamilton path, determine which edges are in the path by asking for each edge i whether there is a Hamiltonian path with weight W for the graph modified so that edge i has weight W + 1 (if there is no such path in the modified graph, then edge i must be in the shortest path for the original graph).

This places the traveling salesman problem in the complexity class FPNP (the class of function problems which can be solved in polynomial time on a deterministic Turing machine with an oracle for a problem in NP), and in fact it is complete for that class.

Last updated: 10-17-2005 14:04:44
03-10-2013 05:06:04
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
Science kits, science lessons, science toys, maths toys, hobby kits, science games and books - these are some of many products that can help give your kid an edge in their science fair projects, and develop a tremendous interest in the study of science. When shopping for a science kit or other supplies, make sure that you carefully review the features and quality of the products. Compare prices by going to several online stores. Read product reviews online or refer to magazines.

Start by looking for your science kit review or science toy review. Compare prices but remember, Price \$ is not everything. Quality does matter.
 Science Fair Coach What do science fair judges look out for? ScienceHound Science Fair Projects for students of all ages
 All Science Fair Projects.com Site All Science Fair Projects Homepage Search | Browse | Links | From-our-Editor | Books | Help | Contact | Privacy | Disclaimer | Copyright Notice