|
PLS (complexity)
In computational complexity theory, Polynomial Local Search (PLS) is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem. The main characteristics of problems that lie in PLS are that the cost of a solution can be calculated in polynomial time and the neighborhood of a solution can be searched in polynomial time. Therefore it is possible to verify whether or not a solution is a local optimum in polynomial time. Furthermore, depending on the problem and the algorithm that is used for solving the problem, it might be faster to find a local optimum instead of a global optimum. Description When searching for a local optimum, there are two interesting issues to deal with: First how to find a local optimum, and second how long it takes to find a local optimum. For many local search algorithms, it is not known, whether they can find a local optimum in polynomial time or not. So to answer the question of how long it takes to find a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Complexity Theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of computationa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pseudo-polynomial Time
In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the ''numeric value'' of the input (the largest integer present in the input)—but not necessarily in the ''length'' of the input (the number of bits required to represent it), which is the case for polynomial time algorithms. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979. In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length. An NP-complete problem with known pseudo-polynomial time algorithms is called weakly NP-complete. An NP-complete problem is called strongly NP-complete if it is proven that it cannot be solved by a pseudo-polynomial time algorithm unless . The strong/weak kinds of NP-hardness are defined anal ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Partition
In mathematics, a graph partition is the reduction of a graph to a smaller graph by partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph. If the number of resulting edges is small compared to the original graph, then the partitioned graph may be better suited for analysis and problem-solving than the original. Finding a partition that simplifies graph analysis is a hard problem, but one that has applications to scientific computing, VLSI circuit design, and task scheduling in multiprocessor computers, among others. Recently, the graph partition problem has gained importance due to its application for clustering and detection of cliques in social, pathological and biological networks. For a survey on recent trends in computational methods and applications see . Two common examples of graph partitioning are minimum cut and maximum cut problems. Problem complexity Typicall ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Boolean Satisfiability Problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called ''satisfiable''. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is ''unsatisfiable''. For example, the formula "''a'' AND NOT ''b''" is satisfiable because one can find the values ''a'' = TRUE and ''b'' = FALSE, which make (''a'' AND NOT ''b'') = TRUE. In contrast, "''a'' AND NOT ''a''" is unsatisfiable. SAT is the first problem that was proved to be NP-complete ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Circuit Satisfiability Problem
In theoretical computer science, the circuit satisfiability problem (also known as CIRCUIT-SAT, CircuitSAT, CSAT, etc.) is the decision problem of determining whether a given Boolean circuit has an assignment of its inputs that makes the output true. In other words, it asks whether the inputs to a given Boolean circuit can be consistently set to 1 or 0 such that the circuit outputs 1. If that is the case, the circuit is called ''satisfiable''. Otherwise, the circuit is called ''unsatisfiable.'' In the figure to the right, the left circuit can be satisfied by setting both inputs to be 1, but the right circuit is unsatisfiable. CircuitSAT is closely related to Boolean satisfiability problem (SAT), and likewise, has been proven to be NP-complete. It is a prototypical NP-complete problem; the Cook–Levin theorem is sometimes proved on CircuitSAT instead of on the SAT, and then CircuitSAT can be reduced to the other satisfiability problems to prove their NP-completeness. The satisfiabi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Co-NP
In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely if only ''no''-instances have a polynomial-length " certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate. That is, co-NP is the set of decision problems where there exists a polynomial ''p(n)'' and a polynomial-time bounded Turing machine ''M'' such that for every instance ''x'', ''x'' is a ''no''-instance if and only if: for some possible certificate ''c'' of length bounded by ''p(n)'', the Turing machine ''M'' accepts the pair (''x'', ''c''). Complementary Problems While an NP problem asks whether a given instance is a ''yes''-instance, its ''complement'' asks whether an instance is a ''no''-instance, which means the complement is in co-NP. Any ''yes''-instance for the original NP ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-hardness
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem. A more precise specification is: a problem ''H'' is NP-hard when every problem ''L'' in NP can be reduced in polynomial time to ''H''; that is, assuming a solution for ''H'' takes 1 unit time, ''H''s solution can be used to solve ''L'' in polynomial time. As a consequence, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. As it is suspected that P≠NP, it is unlikely that such an algorithm exists. It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven. Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class. Defi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
TFNP
In computational complexity theory, the complexity class TFNP is the class of total function problems which can be solved in nondeterministic polynomial time. That is, it is the class of function problems that are guaranteed to have an answer, and this answer can be checked in polynomial time, or equivalently it is the subset of FNP where a solution is guaranteed to exist. The abbreviation TFNP stands for "Total Function Nondeterministic Polynomial". TFNP contains many natural problems that are of interest to computer scientists. These problems include integer factorization, finding a Nash Equilibrium of a game, and searching for local optima. TFNP is widely conjectured to contain problems that are computationally intractable, and several such problems have been shown to be hard under cryptographic assumptions. However, there are no known unconditional intractability results or results showing NP-hardness of TFNP problems. TFNP is not believed to have any complete problems.Goldberg ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
FNP (complexity)
In computational complexity theory, the complexity class FNP is the function problem extension of the decision problem class NP. The name is somewhat of a misnomer, since technically it is a class of binary relations, not functions, as the following formal definition explains: :A binary relation P(''x'',''y''), where ''y'' is at most polynomially longer than ''x'', is in FNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(''x'',''y'') holds given both ''x'' and ''y''. This definition does not involve nondeterminism and is analogous to the verifier definition of NP. There is an NP language directly corresponding to every FNP relation, sometimes called the decision problem ''induced by'' or ''corresponding to'' said FNP relation. It is the language formed by taking all the ''x'' for which P(''x'',''y'') holds given some ''y''; however, there may be more than one FNP relation for a particular decision problem. Many problems in NP, in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
FP (complexity)
In computational complexity theory, the complexity class FP is the set of function problems that can be solved by a deterministic Turing machine in polynomial time. It is the function problem version of the decision problem class P. Roughly speaking, it is the class of functions that can be efficiently computed on classical computers without randomization. The difference between FP and P is that problems in P have one-bit, yes/no answers, while problems in FP can have any output that can be computed in polynomial time. For example, adding two numbers is an FP problem, while determining if their sum is odd is in P. Polynomial-time function problems are fundamental in defining polynomial-time reductions, which are used in turn to define the class of NP-complete problems. Formal definition FP is formally defined as follows: :A binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codom ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP (complexity)
In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.''Polynomial time'' refers to how quickly the number of operations needed by an algorithm, relative to the size of the problem, grows. It is therefore a measure of efficiency of an algorithm. An equivalent definition of NP is the set of decision problems ''solvable'' in polynomial time by a nondeterministic Turing machine. This definition is the basis for the abbreviation NP; " nondeterministic, polynomial time". These two definitions are equivalent because the algorithm based on the Turing machine consists of two phases, the first of which consists of a guess abou ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
