...screte programming, discrete optimization.) Sources of integer programming problems are technology, economy and defense.
...n which the optimization proceeds (for example, the set of permutations in problems of ordering); and c) the presence of logical conditions, which by holding o
5 KB (700 words) - 19:16, 4 November 2014
...]]). Thus, in the theory of (observational) errors, developed by Gauss for problems in astronomy and theoretical geodesy, the probability density of random err
2 KB (312 words) - 16:10, 19 August 2014
...sited (cf. also [[Classical combinatorial problems|Classical combinatorial problems]]). Each city $C_i$ is represented by a point $( x _ { i 1 } , \ldots , x _
...d> <td valign="top"> S. Sahni, T. Gonzales, "P-complete approximation problems" ''J. Assoc. Comput. Mach.'' , '''23''' (1976) pp. 555–565</td></tr>
4 KB (703 words) - 18:40, 7 August 2025
The fundamental concepts, problems and methods which arise in the study of the equivalence of finite automata
4 KB (655 words) - 15:11, 10 August 2014
...suffices to guarantee linear-time algorithms for many otherwise hard graph problems when instances are confined to Halin graphs (e.g. vertex cover, dominating
...neration of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families" ''Algorithmica'' , '''7''' (19
5 KB (722 words) - 20:45, 16 March 2023
...ailable. Consequently, one is tempted to give at least a classification of problems in terms of statements like: one problem is at least as hard to solve as an
...a problem instance. Of particular importance is the class $\mathcal{P}$ of problems solvable in polynomial time. A problem is in $\mathcal{P}$ if it can be dec
7 KB (1,161 words) - 16:46, 1 July 2020
...ut of the set of bounds which defines the class. This branch also includes problems of comparative computational complexity for various types of algorithms (au
...or certain combinatorial problems which are formalized (in one variant) as problems of finding, out of all words of a given word length, those which satisfy a
16 KB (2,413 words) - 16:10, 1 April 2020
...cessors matches the sequential complexity of the problem. Examples of such problems include parallel sorting algorithms running in $O(\log n)$ time using $O(n)
...P$ that are outside $\mathcal{NC}$, where $\mathcal P$ consists of all the problems that can be solved in polynomial sequential time (cf. also [[Complexity the
6 KB (940 words) - 23:19, 25 November 2018
A generic name for a number of very different problems. For instance, suppose that a facility (a "machine" ) starting from an "i
...g "hard" (cf. also [[NP|$\mathcal{NP}$]]). Essentially, for this sort of problems, one does not presently (2000) know of any solution scheme which does not r
4 KB (750 words) - 22:51, 19 April 2012
...ere first introduced by J.C.C. McKinsey in 1943 in the context of decision problems. Their name, Horn clauses, alludes to a paper by A. Horn, who in 1951 was t
...imate language for building expert systems and for formulating and solving problems in artificial intelligence. This enthusiasm for Horn clause logic has been
7 KB (1,111 words) - 06:59, 21 October 2016
...nt difficulty of computational problems. Attention is confined to decision problems, i.e., sets of binary strings, $S \subseteq \Sigma ^ {\color{blue} * }$, wh
...the complexity class $\operatorname {DTIME}[t(n)]$ is the set of decision problems that are computable by a deterministic, multi-tape Turing machine in $O ( t
22 KB (3,236 words) - 06:51, 30 July 2025
...ic and nondeterministic Turing machines. One of the most famous (unsolved) problems in this context is the question, whether the classes of functions calculate
8 KB (1,318 words) - 10:08, 18 February 2021
...e, if the edge probability is not extremely small, the $\cal N P$-complete problems "3-colourability" and "Hamiltonian circuit" can easily be solved, simpl
...d yield efficient solutions for all other problems in this class. Complete problems capture the intrinsic complexity of a class.
21 KB (3,197 words) - 06:28, 31 July 2025
One of the fundamental problems in scheduling is to schedule $n$ independent jobs (tasks) non-pre-emptively
5 KB (739 words) - 16:43, 3 August 2014
...del of computation. Continuous computational complexity studies continuous problems and tends to use the real number model; see [[#References|[a1]]], [[#Refere
...ons, optimization, and solution of non-linear equations. The input of such problems is usually a multivariate function on the real numbers, represented by an o
6 KB (871 words) - 17:45, 1 July 2020
...antum systems, known to be tractable on a quantum computer, relates to the problems conventionally studied within classical computational complexity theory (cf
...n, most comparisons of the quantum and classical complexity of algorithmic problems use bounds on the efficiency of probabilistic algorithms.
14 KB (2,127 words) - 09:45, 18 July 2025
The classification of mathematical problems into decidable and undecidable ones is a most fundamental one. It is also o
...of decidable problems in terms of their complexity is discussed below. Two problems might both be decidable and yet one might be enormously more difficult to c
20 KB (3,105 words) - 17:46, 4 June 2020
...search]]) concerned with mathematical formulations and solution methods of problems of optimal ordering and coordination in time of certain operations. Schedul
...s that scheduling theory deals with are usually formulated as optimization problems for a process of processing a finite set of jobs in a system with limited r
21 KB (3,117 words) - 10:04, 18 February 2021
...annot even exist a public-key cryptosystem whose cryptanalytical task is [[NP-complete]].
...]]. They showed the existence of such proofs for specific number-theoretic problems such as being a [[Quadratic residue|quadratic residue]] or not. Under crypt
35 KB (5,528 words) - 19:33, 19 January 2024
...ring machine can be defined more or less canonically, several conceptional problems associated with it and concerning the notion of 'quantum computation' exist
...s still unknown whether a quantum Turing machine can solve ${\mathrm{NP}}$-problems in $\mathrm{BQP}$.
27 KB (4,213 words) - 18:53, 26 April 2014