Spisu treści:
- Definicja - Co oznacza niedeterministyczny czas wielomianowy (NP)?
- Techopedia wyjaśnia niedeterministyczny czas wielomianowy (NP)
Definicja - Co oznacza niedeterministyczny czas wielomianowy (NP)?
Niedeterministyczny czas wielomianowy (NP) jest tak naprawdę znacznikiem używanym do wskazywania zestawu problemów i granic możliwości niektórych rodzajów obliczeń. NP odnosi się do zestawu problemów, które można rozwiązać w czasie wielomianowym za pomocą niedeterministycznej maszyny Turinga.
Techopedia wyjaśnia niedeterministyczny czas wielomianowy (NP)
Niedeterministyczny czas wielomianowy opiera się na frazie „czas wielomianowy”, który odnosi się do tego, czy algorytm może działać w określonych granicach związanych z prędkością. Czas wielomianowy pojawił się jako sposób mówienia o wykonalności pracy i rozwoju algorytmu.
Jeśli problem występuje w niedeterministycznym czasie wielomianowym, niedeterministyczna maszyna Turinga może najpierw odgadnąć rozwiązanie, a następnie uruchomić weryfikowalny algorytm, który potwierdzi, czy to przypuszczenie było prawidłowe. Programy definiujące na podstawie weryfikatora lub programy definiujące maszynę będą w istocie testować wstępne wybory niedeterministycznej maszyny Turinga w celu weryfikacji wyników.
Wszystko to jest wysoce teoretyczną strukturą obliczeniową. Podczas gdy uczenie maszynowe robi postępy, wykraczając poza systemy deterministyczne, pomysł weryfikacji niedeterministycznych wyborów jest wciąż w powijakach. Poszukaj dalszego rozwoju na tej granicy komputerów.
