Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Transcomputational problem (view)

searching for Computational problem 97 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 (642 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

Closest string (849 words) [view diff] exact match in snippet view article find links to article

theoretical computer science, the closest string is an NP-hard computational problem, which tries to find the geometrical center of a set of input strings

Kronecker substitution (215 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

Tonelli–Shanks algorithm (3,750 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

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:

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.

Data publishing (2,051 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

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,665 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

Sokoban (1,415 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

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

Graph isomorphism (1,638 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

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

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

Property of a computational problem

Clique (graph theory) (2,501 words) [view diff] exact match in snippet view article

minors, respectively. In computer science, the clique problem is the computational problem of finding a maximum clique, or all cliques, in a given graph. It

Universal algebra (3,043 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

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

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

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

Type of computational problem

P versus NP problem (7,784 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

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

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,162 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 (692 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, CiteSeerX 10.1.1.297.3259, doi:10

Computational theory of mind (2,916 words) [view diff] exact match in snippet view article find links to article

levels of description: the computational level, which describes that computational problem solved by the cognitive process; the algorithmic level, which presents

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

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

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,852 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

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

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

Evolutionary algorithm (4,553 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

Protein (10,957 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

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,159 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

Central processing unit (11,424 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,089 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

Colour refinement algorithm (899 words) [view diff] exact match in snippet view article find links to article

Colour refinement can be used as a subroutine for an important computational problem: graph isomorphism. In this problem we have as input two graphs

Gimbal lock (2,644 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:

Set cover problem (2,683 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

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

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

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

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 (4,004 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 – economic equilibrium concept

Quantum supremacy (5,929 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

Turing test (12,541 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

Outline of thought (5,081 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

Computational hardness assumption (3,303 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

Knapsack problem (7,799 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,290 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

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

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 }

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

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

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

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

Differential algebra (7,852 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

Timeline of quantum computing and communication (22,774 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

Third-generation sequencing (3,988 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

Probabilistic numerics (4,271 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

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

Tensor rank decomposition (6,308 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

Ideal lattice (6,061 words) [view diff] exact match in snippet view article find links to article

Poly(n)-Ideal-SVP). The average-case collision-finding problem is a natural computational problem called Ideal-SIS, which has been shown to be as hard as the worst-case

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,856 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