Polinomska ekvivalenca

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Polinomska ekvivalenca ~ je relacija na množici odločitvenih problemov. Definiramo jo takole: Problem P je polinomsko ekvivalenten problemu R natanko tedaj, ko je problem P polinomsko prevedljiv na problem R in je problem R polinomsko prevedljiv na problem P.

Polinomska ekvivalenca je ekvivalenčna relacija, torej velja:

  1. P~P
  2. P~R => R~P
  3. P~R, R~S => P~S

Glej tudi

Osebna orodja