Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Transcomputational problem (view)

searching for computational problem 93 found (173 total)

NP-hardness (1,119 words) [view diff] exact match in snippet view article find links to article

In computational complexity theory, a computational problem H is called NP-hard if, for every problem L which can be solved in non-deterministic polynomial-time

Probabilistic analysis of algorithms (303 words) [view diff] exact match in snippet view article find links to article

approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution

ASR-complete (140 words) [view diff] exact match in snippet view article find links to article

complexity theory, a term to indicate that the difficulty of a computational problem is equivalent to solving the central automatic speech recognition

Gadget (computer science) (1,604 words) [view diff] exact match in snippet view article

fundamental units of a different computational problem. Gadgets are typically used to construct reductions from one computational problem to another, as part of

Combinatorial auction (1,079 words) [view diff] exact match in snippet view article find links to article

game-theoretic challenges compared to traditional auctions. An example of a computational problem is how to efficiently determine the allocation once the bids have

Strong NP-completeness (714 words) [view diff] exact match in snippet view article find links to article

computational problems that is a special case of NP-completeness. A general computational problem may have numerical parameters. For example, the input to the bin

3-dimensional matching (1,550 words) [view diff] exact match in snippet view article find links to article

matching, often abbreviated as 3DM, is also the name of a well-known computational problem: finding a largest 3-dimensional matching in a given hypergraph

Simultaneous localization and mapping (3,878 words) [view diff] exact match in snippet view article find links to article

Simultaneous localization and mapping (SLAM) is the computational problem of constructing or updating a map of an unknown environment while simultaneously

Tonelli–Shanks algorithm (3,751 words) [view diff] exact match in snippet view article find links to article

composite moduli: finding square roots modulo composite numbers is a computational problem equivalent to integer factorization. An equivalent, but slightly

Home prime (870 words) [view diff] exact match in snippet view article find links to article

subject is really one in recreational mathematics. The outstanding computational problem as of 2016[update] is whether HP(49) = HP(77) can be calculated

Gene prediction (3,555 words) [view diff] exact match in snippet view article find links to article

research community, gene finding has been redefined as a largely computational problem. Determining that a sequence is functional should be distinguished

Kronecker substitution (312 words) [view diff] exact match in snippet view article find links to article

representation of p(x). One application of this method is to reduce the computational problem of multiplying polynomials to the (potentially simpler) problem

Floating-point error mitigation (1,109 words) [view diff] exact match in snippet view article find links to article

measured in petaflops, floating-point error is a major concern for computational problem solvers. The following sections describe the strengths and weaknesses

Fine-grained reduction (831 words) [view diff] exact match in snippet view article find links to article

complexity theory, a fine-grained reduction is a transformation from one computational problem to another, used to relate the difficulty of improving the time

Xuong tree (387 words) [view diff] exact match in snippet view article find links to article

graph in polynomial time, by a transformation to a more general computational problem on matroids, the matroid parity problem for linear matroids. Beineke

Query complexity (244 words) [view diff] exact match in snippet view article find links to article

computational complexity describes the number of queries needed to solve a computational problem for an input that can be accessed only through queries. See in particular:

Mordell–Weil theorem (619 words) [view diff] exact match in snippet view article find links to article

unanswered: Calculation of the rank. This is still a demanding computational problem, and does not always have effective solutions. Meaning of the rank:

Data publishing (2,056 words) [view diff] exact match in snippet view article find links to article

emerging topic in computer science and it has been defined as a computational problem. Indeed, citing data poses significant challenges to computer scientists

Joseph Zachary (343 words) [view diff] case mismatch in snippet view article find links to article

Zachary, Joseph L. (1996). Introduction to Scientific Programming: Computational Problem Solving Using Maple and C. Springer-Verlag. ISBN 0-387-94630-6.

Parallel parking problem (190 words) [view diff] exact match in snippet view article find links to article

Robotics and planning computational problem

Economic materialism (1,657 words) [view diff] exact match in snippet view article find links to article

quality of life Reduction (complexity) – Transformation of one computational problem to another Conspicuous consumption – Concept in sociology and economy

General-purpose programming language (1,495 words) [view diff] exact match in snippet view article find links to article

Turing complete, meaning that they can theoretically solve any computational problem. Domain-specific languages are often similarly Turing complete but

Shifted force method (983 words) [view diff] exact match in snippet view article find links to article

interactions are long-range in nature, presenting a challenging computational problem in the simulation of particulate systems. To determine the net forces

Minkowski's theorem (2,350 words) [view diff] exact match in snippet view article find links to article

certain magnitude bound, finding this vector is in general a hard computational problem. Finding the vector within a factor guaranteed by Minkowski's bound

Nondeterministic Turing machine (1,626 words) [view diff] exact match in snippet view article find links to article

but every branch must reject for the string to be rejected. Any computational problem that can be solved by a DTM can also be solved by a NTM, and vice

Graph isomorphism (1,637 words) [view diff] exact match in snippet view article find links to article

it is a problem to be tackled with an algorithmic approach. The computational problem of determining whether two finite graphs are isomorphic is called

Genome project (1,822 words) [view diff] exact match in snippet view article find links to article

and the process continues. Genome assembly is a very difficult computational problem, made more difficult because many genomes contain large numbers

Optimal substructure (742 words) [view diff] exact match in snippet view article find links to article

Property of a computational problem

Polynomial-time reduction (1,472 words) [view diff] exact match in snippet view article find links to article

\mathbb {R} } defined from the existential theory of the reals, a computational problem that is known to be NP-hard and in PSPACE, but is not known to be

Occupancy grid mapping (651 words) [view diff] exact match in snippet view article find links to article

p(m_{i})} represents the probability that cell i is occupied. The computational problem with estimating the posterior p ( m ∣ z 1 : t , x 1 : t ) {\displaystyle

Covering problems (938 words) [view diff] exact match in snippet view article find links to article

Type of computational problem

Universal algebra (3,021 words) [view diff] exact match in snippet view article find links to article

existential sentence φ {\displaystyle \varphi } . It is proved that every computational problem can be formulated as CSPA for some algebra A. For example, the n-coloring

Fractional job scheduling (1,605 words) [view diff] exact match in snippet view article find links to article

performance, for example, decreasing the makespan. Moreover, the computational problem of finding an optimal schedule may become easier, as some of the

Percolation theory (3,133 words) [view diff] exact match in snippet view article find links to article

degree distribution follows a power law Shortest path problem – Computational problem of graph theory Broadbent, Simon; Hammersley, John (1957). "Percolation

P versus NP problem (7,797 words) [view diff] exact match in snippet view article find links to article

in P or to be NP-complete. The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. An important

Cluster graph (647 words) [view diff] exact match in snippet view article find links to article

cluster graphs are exactly the graphs of subchromatic number 1. The computational problem of finding a small set of edges to add or remove from a graph to

Structure formation (2,171 words) [view diff] exact match in snippet view article find links to article

cooling. Understanding these processes is an enormously difficult computational problem, because they can involve the physics of gravity, magnetohydrodynamics

Lila Kari (696 words) [view diff] exact match in snippet view article find links to article

(1999), "The evolution of cellular computing: Nature's solution to a computational problem", Biosystems, 52 (1–3): 3–13, Bibcode:1999BiSys..52....3L, CiteSeerX 10

Peter Buneman (1,067 words) [view diff] case mismatch in snippet view article find links to article

Peter Buneman, Susan Davidson, James Frew. "Why Data Citation Is a Computational Problem". cacm.acm.org. ACM Press. Retrieved 15 February 2024.{{cite web}}:

Flow-shop scheduling (901 words) [view diff] exact match in snippet view article find links to article

Class of computational problem

Sokoban (3,204 words) [view diff] exact match in snippet view article find links to article

been studied using the theory of computational complexity. The computational problem of solving Sokoban puzzles was first shown to be NP-hard. Further

Leximin order (1,591 words) [view diff] exact match in snippet view article find links to article

lexicographic order. Lexicographic max-min optimization is the computational problem of finding a maximal element of the leximin order in a given set

Lattice-based cryptography (2,872 words) [view diff] exact match in snippet view article find links to article

{\displaystyle \mathbb {Z} ^{3}} . The most important lattice-based computational problem is the shortest vector problem (SVP or sometimes GapSVP), which

Scientific programming language (756 words) [view diff] case mismatch in snippet view article find links to article

2025. Zachary, Joseph. "Introduction to Scientific Programming: Computational Problem Solving Using Maple and C". University of Utah. Retrieved 13 May

Subway Challenge (2,679 words) [view diff] exact match in snippet view article find links to article

Challenge, a similar challenge in London Travelling salesman problem, a computational problem where the goal is to find the shortest route that runs through all

ChIP sequencing (3,353 words) [view diff] exact match in snippet view article find links to article

ChIP-seq peak-calling tools by Thomas et al. (2017). Another relevant computational problem is differential peak calling, which identifies significant differences

Evolutionary algorithm (4,543 words) [view diff] exact match in snippet view article find links to article

programs, and their fitness is determined by their ability to solve a computational problem. There are many variants of Genetic Programming: Cartesian genetic

Erdős–Pósa theorem (1,324 words) [view diff] exact match in snippet view article find links to article

set of vertices whose removal destroys all cycles. This is a hard computational problem; if we are not able to solve it exactly, we can instead try to find

Regular number (3,277 words) [view diff] exact match in snippet view article find links to article

1972 hailed Inaqibıt-Anu as "the first man in history to solve a computational problem that takes longer than one second of time on a modern electronic

Complexity and Real Computation (852 words) [view diff] exact match in snippet view article find links to article

to provide a lower bound on the time complexity of an associated computational problem. The book is aimed at the level of a graduate student or researcher

Carathéodory's theorem (convex hull) (2,343 words) [view diff] exact match in snippet view article

extended this colorful theorem from points to convex bodies. The computational problem of finding the colorful set lies in the intersection of the complexity

Protein (10,974 words) [view diff] exact match in snippet view article find links to article

important part of protein structure characterisation. A more complex computational problem is the prediction of intermolecular interactions, such as in molecular

Central processing unit (11,434 words) [view diff] exact match in snippet view article find links to article

applications, so-called "embarrassingly parallel problems". Frequently, a computational problem that can be solved quickly with high TLP design strategies like

Bin packing problem (7,098 words) [view diff] exact match in snippet view article find links to article

for example, minimizing the number of total bin. Moreover, the computational problem of finding an optimal schedule may become easier, as some of the

Gimbal lock (2,650 words) [view diff] exact match in snippet view article find links to article

system – Continuously computed dead reckoning Motion planning – Computational problem Quaternions and spatial rotation – Correspondence between quaternions

Ham sandwich theorem (2,708 words) [view diff] exact match in snippet view article find links to article

In computational geometry, this ham sandwich theorem leads to a computational problem, the ham sandwich problem. In two dimensions, the problem is this:

Computational social choice (1,538 words) [view diff] exact match in snippet view article find links to article

complexity shields against manipulation are less effective. Another computational problem associated with preference restrictions is that of recognizing when

Read (biology) (2,055 words) [view diff] exact match in snippet view article

sequencing" (SRS). After sequencing short reads, it then becomes a computational problem and many computer programs and techniques have been developed to

Set cover problem (3,011 words) [view diff] exact match in snippet view article find links to article

Red-blue set cover. Set-cover abduction. Monotone dualization is a computational problem equivalent to either listing all minimal hitting sets or listing

Competitive equilibrium (3,841 words) [view diff] exact match in snippet view article find links to article

unit-demand valuations coupled with the given non-GS valuation. For the computational problem of finding a competitive equilibrium in a special kind of a market

Matroid intersection (1,822 words) [view diff] exact match in snippet view article find links to article

in G, ensuring that the selected edge set has no cycles. Another computational problem on matroids, the matroid parity problem, was formulated by Lawler

Bellman equation (3,990 words) [view diff] exact match in snippet view article find links to article

output from a dynamic system Optimal substructure – Property of a computational problem Recursive competitive equilibrium Stochastic dynamic programming –

Addition (10,217 words) [view diff] exact match in snippet view article find links to article

the reciprocal value of a sum of reciprocal values Prefix sum, computational problem of finding running totals Pythagorean addition, combining two side

Turing test (12,615 words) [view diff] exact match in snippet view article find links to article

deliberately avoid appearing too intelligent. If it were to solve a computational problem that is practically impossible for a human to solve, then the interrogator

Computational hardness assumption (3,302 words) [view diff] exact match in snippet view article find links to article

functional encryption (multilinear jigsaw puzzles) The most fundamental computational problem on lattices is the shortest vector problem (SVP): given a lattice

Quantum supremacy (5,940 words) [view diff] exact match in snippet view article find links to article

called NISQ devices. Such proposals include (1) a well-defined computational problem, (2) a quantum algorithm to solve this problem, (3) a comparison

Outline of thought (5,215 words) [view diff] exact match in snippet view article find links to article

starting point for solving it Reduction – Transformation of one computational problem to another – transforming the problem into another problem for which

Knapsack problem (7,744 words) [view diff] exact match in snippet view article find links to article

Computer programming portal Bin packing problem – Mathematical and computational problem Change-making problem – Choosing the fewest coins to make a given

Homomorphic encryption (4,692 words) [view diff] exact match in snippet view article find links to article

BLLN schemes that rely on an overstretched variant of the NTRU computational problem. This NTRU variant was subsequently shown vulnerable to subfield

K-server problem (1,379 words) [view diff] exact match in snippet view article find links to article

Computational problem of interest in computer science

Chromatic polynomial (4,325 words) [view diff] exact match in snippet view article find links to article

question if some of the coefficients are easy to compute. However the computational problem of computing ar for a fixed r ≥ 1 and a given graph G is #P-hard

Envy-free pricing (2,559 words) [view diff] exact match in snippet view article find links to article

help the seller attain a higher revenue. Many authors studied the computational problem of finding a price-vector that maximizes the seller's revenue, subject

Pseudo-polynomial transformation (1,044 words) [view diff] exact match in snippet view article find links to article

O(\log(n))} . Suppose that L {\displaystyle L} is an encoding of a computational problem Π {\displaystyle \Pi } over alphabet Σ {\displaystyle \Sigma }

Natural computing (5,191 words) [view diff] exact match in snippet view article find links to article

L. The evolution of cellular computing: Nature's solution to a computational problem[permanent dead link]. Biosystems, 52, 1/3 (1999) 3-13. Angeleska

Small Latin squares and quasigroups (3,515 words) [view diff] exact match in snippet view article find links to article

Finding a given Latin square's isomorphism class can be a difficult computational problem for squares of large order. To reduce the problem somewhat, a Latin

Optimal network design (581 words) [view diff] exact match in snippet view article find links to article

terminals are connected, but pay as little as possible. They study the computational problem of checking whether a Nash equilibrium exists. For some special

Blichfeldt's theorem (1,935 words) [view diff] exact match in snippet view article find links to article

replace the single set S {\displaystyle S} with a family of sets. A computational problem related to Blichfeldt's theorem has been shown to be complete for

Perfect graph (7,055 words) [view diff] exact match in snippet view article find links to article

separation oracle. Beyond solving these problems, another important computational problem concerning perfect graphs is their recognition, the problem of testing

Timeline of quantum computing and communication (22,807 words) [view diff] exact match in snippet view article find links to article

secure communication. David Deutsch and Richard Jozsa propose a computational problem that can be solved efficiently with the deterministic Deutsch–Jozsa

Differential algebra (7,853 words) [view diff] exact match in snippet view article find links to article

Ovchinnikov, A. I. (2009). "On the generalized Ritt problem as a computational problem". Journal of Mathematical Sciences. 163 (5): 515–522. arXiv:0809

Third-generation sequencing (4,039 words) [view diff] exact match in snippet view article find links to article

generation of sequencing technologies, de novo assembly is a major computational problem. It is normally approached by an iterative process of finding and

Massively parallel communication (797 words) [view diff] exact match in snippet view article find links to article

consisting of S {\displaystyle S} words of memory. The input to a computational problem in this model is distributed arbitrarily across all of the machines

Probabilistic numerics (4,270 words) [view diff] exact match in snippet view article find links to article

Bayesian inference). Formally, this means casting the setup of the computational problem in terms of a prior distribution, formulating the relationship between

Tensor rank decomposition (6,321 words) [view diff] exact match in snippet view article find links to article

Romani, F. (1980). "Approximate solutions for the bilinear form computational problem". SIAM Journal on Scientific Computing. 9 (4): 692–697. doi:10.1137/0209053

Generalized distributive law (6,400 words) [view diff] exact match in snippet view article find links to article

the concepts. MPF or marginalize a product function is a general computational problem which as special case includes many classical problems such as computation

PLS (complexity) (5,471 words) [view diff] exact match in snippet view article

the first swap of the Fiduccia-Mattheyses. Consider the following computational problem: Given some instance I {\displaystyle I} of a PLS problem L {\displaystyle

Kernel methods for vector output (4,220 words) [view diff] exact match in snippet view article find links to article

classification and used to find estimates for the hyperparameters. The main computational problem in the Bayesian viewpoint is the same as the one appearing in regularization

Fair allocation of items and money (3,957 words) [view diff] exact match in snippet view article find links to article

polynomial time using value-queries. Caragiannis and Ioannidis study the computational problem of minimizing the subsidy: For a constant number of agents, they

Phylogenetic reconciliation (15,304 words) [view diff] exact match in snippet view article find links to article

replaced by a single transfer. One of the first ideas to define a computational problem and approach a resolution was, in a host/symbiont framework, to

Thiele's voting rules (1,657 words) [view diff] exact match in snippet view article find links to article

general, solving the global optimization problem is an NP-hard computational problem, except when f(r)=r. Therefore, Thiele suggested two greedy approximation

Small set expansion hypothesis (1,502 words) [view diff] exact match in snippet view article find links to article

application of the small set expansion hypothesis concerns the computational problem of approximating the treewidth of graphs, a structural parameter

Optimal kidney exchange (1,857 words) [view diff] exact match in snippet view article find links to article

cycles of length at most k, for any fixed k ≥ 3, is an NP-hard computational problem (this can be proved by reduction from the problem of 3-dimensional

SIRIUS (software) (5,859 words) [view diff] exact match in snippet view article

fragmentation tree similarity. Finding an optimal solution to the resulting computational problem is NP-hard, therefore Gibbs sampling is used. ZODIAC stands for