Can Randomness Improve Computational Power for Turing Machines?

[infoman]

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.

 

[verty]

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?

 

[-Job-]

...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.

 

[verdigris]

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.