About: Computational problem

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Computational problem Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Planet, within Data Space : el.dbpedia.org associated with source document(s)

In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring "Given a positive integer n, find a nontrivial prime factor of n." is a computational problem. A computational problem can be viewed as a set of instances or cases together with a, possibly empty, set of solutions for every instance/case. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbers p that describe nontrivial prime factors of n.

Attributes	Values
rdf:type	planet
rdfs:label	Computational problem (en)
rdfs:comment	In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring "Given a positive integer n, find a nontrivial prime factor of n." is a computational problem. A computational problem can be viewed as a set of instances or cases together with a, possibly empty, set of solutions for every instance/case. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbers p that describe nontrivial prime factors of n. (en)
sameAs	Computational problem Computational problem
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Efn dbt:Main dbt:No_footnotes dbt:Notelist dbt:Short_description
Subject	Computational problems Theoretical computer science
gold:hypernym	Object
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Computational_problem?oldid=1071122850&ns=0
Wikipage page ID	4594672 (xsd:integer)
page length (characters) of wiki page	7201 (xsd:nonNegativeInteger)
Wikipage revision ID	1071122850 (xsd:integer)
Link from a Wikipage to another Wikipage	NP-hardness Promise problem Property testing Undecidable problem Abstract machine Algorithm Analysis of algorithms BQP Cambridge University Press Computational problems Theoretical computer science P (complexity) Search problem Set (mathematics) Decision problem Primality test The Princeton Companion to Mathematics Combinatorial optimization Complexity class Computational complexity Algorithmic complexity Counting problem (complexity) Operations research Optimization problem Partial function Function problem Independent set (graph theory) Hardness of approximation Integer factorization Interactive proof system Model of computation Transcomputational problem Travelling salesman problem String (computer science) Theoretical computer science Lateral computing Regular expression Relation (mathematics)
has abstract	In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring "Given a positive integer n, find a nontrivial prime factor of n." is a computational problem. A computational problem can be viewed as a set of instances or cases together with a, possibly empty, set of solutions for every instance/case. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbers p that describe nontrivial prime factors of n. Computational problems are one of the main objects of study in theoretical computer science. The field of computational complexity theory attempts to determine the amount of resources (computational complexity) solving a given problem will require and explain why some problems are intractable or undecidable. Computational problems belong to complexity classes that define broadly the resources (e.g. time, space/memory, energy, circuit depth) it takes to compute (solve) them with various abstract machines. For example, the complexity class P for cassical machines, and BQP for quantum machines. It is typical of many problems to represent both instances and solutions by binary strings, namely elements of {0, 1}*. For example, numbers can be represented as binary strings using binary encoding. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Computational_problem
is Wikipage redirect of	Computational problems Computation problem
is Link from a Wikipage to another Wikipage of	List of undecidable problems Market equilibrium computation NSPACE Non-constructive algorithm existence proofs Numberlink 2-satisfiability Algorithm Analysis of algorithms And–or tree Anytime algorithm Approximation-preserving reduction Asymptotic computational complexity Automata theory Backtracking Binary decision diagram Binary search tree Biodiversity informatics Generic-case complexity Glossary of areas of mathematics Glossary of artificial intelligence Glossary of computer science Distributed computing Metagame analysis Micah Altman Chronology of the universe Circuit complexity DLOGTIME Turing machine DTIME Decision problem Decomposition (computer science) K-line (artificial intelligence) Collision detection Complete (complexity) Complexity class Computability Computability logic Computation Computational complexity Algorithmic complexity

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software