Spis treści
21 kontakty: Algorytm pseudowielomianowy, Dowód z wiedzą zerową, DTIME, Graf doskonały, Klasa Co-NP, Klasa złożoności, Kryptologia, Kubit pomocniczy, L (klasa złożoności), P (ujednoznacznienie), Problem NP, Problem NP-pośredni, Problem silnie NP-zupełny, Problem spełnialności, Programowanie dynamiczne, Proporcjonalna metoda głosowania przez aprobaty, PSPACE, Teoria liczb, Test pierwszości, Teza Edmondsa, Złożoność obliczeniowa.
Algorytm pseudowielomianowy
Algorytm pseudowielomianowy – algorytm, którego złożoność obliczeniowa jest pseudowielomianowa.
Zobaczyć Problem P i Algorytm pseudowielomianowy
Dowód z wiedzą zerową
Dowód z wiedzązerową– procedura kryptograficzna, w której jedna ze stron potrafi udowodnić drugiej, że dysponuje pewnąinformacją, bez jej ujawniania.
Zobaczyć Problem P i Dowód z wiedzą zerową
DTIME
W teorii złożoności obliczeniowej DTIME jest klasązłożoności czasowej dla deterministycznej maszyny Turinga.
Zobaczyć Problem P i DTIME
Graf doskonały
Graf doskonały – graf w którym liczba chromatyczna każdego podgrafu indukowanego (wierzchołkowo) jest równa rozmiarowi największej kliki tego podgrafu.
Zobaczyć Problem P i Graf doskonały
Klasa Co-NP
Klasa Co-NP – klasa złożoności dopełniająca dla problemów decyzyjnych NP.
Zobaczyć Problem P i Klasa Co-NP
Klasa złożoności
Klasa złożoności – zbiór problemów obliczeniowych o podobnej złożoności obliczeniowej.
Zobaczyć Problem P i Klasa złożoności
Kryptologia
II wojny światowej do szyfrowania wiadomości sztabowych wysokiego szczebla Kryptologia (z gr. κρυπτός kryptos, „ukryty”, i λόγος logos, „rozum”, „słowo”) – dziedzina wiedzy o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem.
Zobaczyć Problem P i Kryptologia
Kubit pomocniczy
Kubit pomocniczy (ang. Ancilla bit) – dodatkowy kubit stosowany w algorytmach kwantowych i zwykle inicjowany stanem standardowym (zwykle |0\rangle lub |1\rangle), którego celem jest zwiększenie wymiaru przestrzeni Hilberta koniecznej do obliczeń.
Zobaczyć Problem P i Kubit pomocniczy
L (klasa złożoności)
W obliczeniowej teorii złożoności L (znane również jako LSPACE lub DLOGSPACE) jest klasązłożoności zawierającąproblemy decyzyjne, które można rozwiązać za pomocądeterministycznej maszyny Turinga przy użyciu logarytmicznej ilości zapisywalnej przestrzeni pamięci.
Zobaczyć Problem P i L (klasa złożoności)
P (ujednoznacznienie)
100px P – szesnasta litera alfabetu łacińskiego, dwudziesta druga litera alfabetu polskiego.
Zobaczyć Problem P i P (ujednoznacznienie)
Problem NP
LadneraR.E. Ladner, ''On the structure of polynomial time reducibility'', J.ACM, 22, 1975, s. 151–171. Corollary 1.1. http://portal.acm.org/citation.cfm?id.
Zobaczyć Problem P i Problem NP
Problem NP-pośredni
Problem NP-pośredni (NPI) – problem decyzyjny należący do klasy NP, który nie należy ani do klasy NPC, ani do klasy P. Jeśli P \neq NP, to klasa NPI zawiera nieskończenie wiele problemów, a jeśli P.
Zobaczyć Problem P i Problem NP-pośredni
Problem silnie NP-zupełny
Problem silnie NP-zupełny to taki problem decyzyjny, który nawet przy ograniczeniu maksymalnej wartości występujących w jego opisie liczb pozostaje NP-zupełny.
Zobaczyć Problem P i Problem silnie NP-zupełny
Problem spełnialności
Problem spełnialności – zagadnienie rachunku zdań, określające czy dla danej formuły logicznej istnieje takie podstawienie (wartościowanie) zmiennych zdaniowych, żeby formuła była prawdziwa.
Zobaczyć Problem P i Problem spełnialności
Programowanie dynamiczne
Programowanie dynamiczne – technika lub strategia projektowania algorytmów, stosowana przeważnie do rozwiązywania zagadnień optymalizacyjnych.
Zobaczyć Problem P i Programowanie dynamiczne
Proporcjonalna metoda głosowania przez aprobaty
Proporcjonalna metoda głosowania przez aprobaty (PGA) (ang.) – proporcjonalny system wyboru komitetów (czyli grup reprezentantów) w drodze głosowania.
Zobaczyć Problem P i Proporcjonalna metoda głosowania przez aprobaty
PSPACE
W teorii złożoności obliczeniowej PSPACE jest zbiorem wszystkich problemów decyzyjnych, które można rozwiązać za pomocąmaszyny Turinga wykorzystującej wielomianowąprzestrzeń.
Zobaczyć Problem P i PSPACE
Teoria liczb
Czeski znaczek pocztowy upamiętniający wielkie twierdzenie Fermata i jego dowód przez Andrew Wilesa Teoria liczb – dziedzina matematyki badająca własności niektórych typów liczbLiczby kardynalne i porządkowe sąbadane przez teorię mnogości.
Zobaczyć Problem P i Teoria liczb
Test pierwszości
Test pierwszości – algorytm określający, czy dana liczba jest pierwsza, czy złożona.
Zobaczyć Problem P i Test pierwszości
Teza Edmondsa
Teza Edmondsa, znana również jako teza Cobhama-Edmondsa (od Alana Cobhama i Jacka Edmondsa)Edmonds, Jack (1965).
Zobaczyć Problem P i Teza Edmondsa
Złożoność obliczeniowa
Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych.
Zobaczyć Problem P i Złożoność obliczeniowa
Znany jako Klasa P, Klasa złożoności P.