Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Computational challenges

  1. Jan 16, 2007 #1
    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: Jan 16, 2007
  2. jcsd
  3. Jan 16, 2007 #2


    User Avatar
    Homework Helper

    From wikipedia:
  4. Jan 18, 2007 #3


    User Avatar
    Science Advisor

    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.
  5. Feb 11, 2007 #4
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook