Computational challenges

  • Thread starter infoman
  • Start date
  • #1
1
0

Main Question or Discussion Point

I would like to start a discussion that summarizes the main computational challenges regarding Turing machines, so my question is: what are the current computational problems which are widely recognized do not have any efficient solution in a probabilistic turing machine.

Maybe you can answer this just giving a reference.
 
Last edited:

Answers and Replies

  • #2
verty
Homework Helper
2,164
198
From wikipedia:
One of the central questions of complexity theory is whether randomness adds power; that is, is there a problem which can be solved in polynomial time by a probabilistic Turing machine but not a deterministic Turing machine?
 
  • #3
-Job-
Science Advisor
1,146
1
...what are the current computational problems which are widely recognized do not have any efficient solution in a probabilistic turing machine.

Maybe you can answer this just giving a reference.
Do you mean "deterministic" instead of "probabilistic"?
An "efficient algorithm" is taken to mean an algorithm that scales polynomially, or less, for any given input. There is a class of problems, "NP", which stands for non-deterministic polynomial time, and which contains problems that currently cannot be solved in a deterministic manner and in polynomial time on a turing machine (or equivalent).
In short, NP contains problems which we currently can't solve efficiently on a traditional computer. Examples of these problems are:
* Boolean satisfiability problem (SAT)
* N-puzzle
* Knapsack problem
* Hamiltonian cycle problem
* Traveling salesman problem
* Subgraph isomorphism problem
* Subset sum problem
* Clique problem
* Vertex cover problem
* Independent set problem
* Graph coloring problem
and... MineSweeper, plus a variety of puzzle games.
 
  • #4
118
0
If an algorithm is written to solve a problem and the algorithm is changed randomly,then provided there is another algorithm that can decide if the change is producing useful results then,yes,randomness can lead to an increase in computing power.
 

Related Threads on Computational challenges

  • Last Post
Replies
22
Views
4K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
2
Replies
25
Views
3K
Replies
4
Views
2K
Replies
3
Views
1K
Replies
12
Views
8K
Replies
31
Views
3K
Top