Research Interests: Preliminaries_Definition

In computational complexity theory, the complexity class NP-complete, also known as NP-C or NPC, is a subset of NP ("non-deterministic polynomial time") [1]; they are the most difficult problems in NP in the sense that a deterministic, polynomial-time solution to any NP-complete problem would provide a solution to every other problem in NP (and conversely, if any one of them provably lacks a deterministic polynomial-time solution, none of them has one). Problems in NP-complete are known as NP-complete problems. A more formal definition is given below.

Definition1 NP-complete [2]

Definition: The complexity class of decision problems for which answers can be checked for correctness, given a certificate, by an algorithm whose run time is polynomial in the size of the input (that is, it is NP) and no other NP problem is more than a polynomial factor harder. Informally, a problem is NP-complete if answers can be verified quickly, and a quick algorithm to solve this problem can be used to solve all other NP problems quickly.

Definition2 NP-hard [3]

Definition: The complexity class of decision problems that are intrinsically harder than those that can be solved by a nondeterministic Turing machine in polynomial time. When a decision version of a combinatorial optimization problem is proved to belong to the class of NP-complete problems, then the optimization version is NP-hard.

Definition3 Optimization problem [4]

Definition: A computational problem in which the object is to find the best of all possible solutions. More formally, find a solution in the feasible region which has the minimum (or maximum) value of the objective function.

{See decision problem, optimal solution, optimal value, geometric optimization problem, witness, local optimum, global optimum, Classical optimization problems: bin packing problem, knapsack problem, cutting stock problem, Chinese postman problem, traveling salesman, vehicle routing problem, prisoner’s dilemma, Solution methods: dynamic programming, metaheuristic, relaxation, simulated annealing.}

Definition4 Knapsack problem (classic problem) [5]

Definition: Given items of different values and volumes, find the most valuable set of items that fit in a knapsack of fixed volume.

Formal Definition: There is a knapsack of capacity c > 0 and N items. Each item has value v_i > 0 and weight w_i > 0. Find the selection of items (δ_i = 1 if selected, 0 if not) that fit, ∑_i=1^N δ_iw_i ≤ c, and the total value, ∑_i=1^N δ_iv_i, is maximized.

Definition5 Metaheuristic (algorithmic technique) [6]

Definition: (1) A high-level algorithmic framework or approach that can be specialized to solve optimization problems. (2) A high-level strategy that guides other heuristics in a search for feasible solutions.

Definition6 Simulated annealing (algorithm) [7]

Definition: A technique to find a good solution to an optimization problem by trying random variations of the current solution. A worse variation is accepted as the new solution with a probability that decreases as the computation proceeds. The slower the cooling schedule, or rate of decrease, the more likely the algorithm is to find an optimal or near-optimal solution.

Definition7 Dynamic programming (algorithmic technique) [8]

Definition: Solve an optimization problem by caching subproblem solutions (memoization) rather than recomputing them.

Note: From Algorithms and Theory of Computation Handbook, page 1-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Definition8 Relaxation [9]

Definition: An optimization problem with an enlarged feasible region (and extended objective function) compared with an original optimization problem. Typically, the relaxation is considerably easier to solve than the original.

Note: From Algorithms and Theory of Computation Handbook, pages 32-39 and 34-18, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Reference

 [1] http://en.wikipedia.org/wiki/NP-complete

 [2] http://www.nist.gov/dads/HTML/npcomplete.html

 [3] http://www.nist.gov/dads/HTML/nphard.html

 [4] http://www.nist.gov/dads/HTML/optimization.html

 [5] http://www.nist.gov/dads/HTML/knapsackProblem.html

 [6] http://www.nist.gov/dads/HTML/metaheuristic.html

 [7] http://www.nist.gov/dads/HTML/simulatedAnnealing.html

 [8] http://www.nist.gov/dads/HTML/dynamicprog.html

 [9] http://www.nist.gov/dads/HTML/relaxation.html