Podaj nick
Dany
jest problem: Dla danej liczby n, czy istnieje co najmniej n liczb
bliźniaczych (to znaczy takich p, że p oraz p+2 są pierwsze).
| | Ten problem jest nierozstrzygalny | | 4 | 10% | | Ten problem jest w NPSPACE (czyli w PSPACE) | | 3 | 8% | | Ten problem jest w NP | | 9 | 23% | | Ten problem jest w P | | 10 | 26% | | Ten problem jest co-NP trudny | | 0 | 0% | | Złożoność tego problemu jest sprawą otwartą | | 12 | 31% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Czemu na JFIZO nie mówi się o klasie problemów rozwiązywalnych w stałej pamięci? |
| | Z braku czasu | | 3 | 8% | | Bo nic o tej klasie nie wiadomo | | 0 | 0% | | Bo ta klasa jest mało ciekawa | | 13 | 33% | | Mówi się, ale nazywa się ją inaczej | | 18 | 46% | | Mówi się, ale tylko po 22 | | 5 | 13% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
O
pewnym problemie wiemy, że istnieją dla niego dwie heurystyki h1 i h2
działające w czasie wielomianowym, takie, że dla dowolnego wejścia co
najmniej jedna z tych heurystyk zwraca poprawną odpowiedź |
| | Zatem ten problem jest w P | | 13 | 34% | | Zatem ten problem jest w NP | | 5 | 13% | | Zatem ten problem jest w NEXPSPACE | | 0 | 0% | | Zatem ten problem jest rozstrzygalny | | 5 | 13% | | Żadne z powyższych | | 15 | 39% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Kto był idiotą zupełnym? |
| | Dziennikarz, który wszedł w czasie wykładu | | 6 | 16% | | Słoń | | 1 | 3% | | Policjant | | 2 | 5% | | Generał | | 19 | 50% | | Menelski | | 10 | 26% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Jaką
złożoność ma następujący problem: dla danego niedeterministycznego
automatu skończonego, czy istnieje słowo akceptowane przez ten automat? |
| | To jest w P | | 22 | 58% | | To jest w NP | | 6 | 16% | | To jest NP-zupełne | | 2 | 5% | | To jest PSPACE-zupełne | | 6 | 16% | | To jest nierozstrzygalne | | 2 | 5% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Jaką
złożoność ma następujący problem: dla danych dwóch
niedeterministycznych automatów skończonych, czy istnieje słowo
akceptowane przez oba automaty? |
| | To jest w P | | 16 | 42% | | To jest w NP | | 7 | 18% | | To jest NP-zupełne | | 5 | 13% | | To jest PSPACE-zupełne | | 5 | 13% | | To jest nierozstrzygalne | | 5 | 13% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Jaką
złożoność ma następujący problem: dla danych n niedeterministycznych
automatów skończonych, czy istnieje słowo akceptowane przez każdy z
tych automatów? |
| | To jest w P | | 8 | 21% | | To jest w NP | | 10 | 26% | | To jest NP-zupełne | | 9 | 24% | | To jest PSPACE-zupełne | | 6 | 16% | | To jest nierozstrzygalne | | 5 | 13% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Przypuśćmy,
że o problemie P wiemy, że istnieje maszyna, która rozstrzyga prawie
rozstrzyga P, tzn. zawsze się zatrzymuje i odpowiada dobrze na pytania
o P dla prawie wszystkich danych wejściowych |
| | P jest rekurencyjnie przeliczalny | | 7 | 18% | | P jest rekurencyjny | | 15 | 39% | | P jest rekurencyjny pod warunkiem, że tamta maszyna działa w czasie wielomianowym | | 1 | 3% | | P jest nierozstrzygalny | | 8 | 21% | | Żadne z powyższych | | 7 | 18% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Ilu liczników potrzebuje automat ze stosem, aby móc symulować dowolną maszynę Turinga? |
| | 1 | | 5 | 13% | | 2 | | 21 | 55% | | 3 | | 6 | 16% | | 4 | | 2 | 5% | | n | | 4 | 11% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Szef
kazał Panu Stefanowi rozwiązać problem, który jest łatwo redukowalny do
3-SATa. Która z poniższych czynności najbardziej pomoże Panu Stefanowi? |
| | Zapisanie się do Okienka Praca na naszej klasie | | 6 | 16% | | Wpisanie w google "P=NP constructive proof" | | 4 | 11% | | Stworzenie głupiego quizu w Internecie | | 3 | 8% | | Wpisanie w google "SAT SOLVER" | | 22 | 58% | | Przeglądanie losowych artykułów na wikipedii | | 1 | 3% | | Sprawdzenie nowości na wykopie | | 2 | 5% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Teraz łatwe pytanie: Problem spełnialności formuł w DNF jest: |
| | NP-zupełny | | 6 | 16% | | w P | | 24 | 63% | | co-NP zupełny | | 3 | 8% | | NPSPACE-zupełny | | 0 | 0% | | nierozstrzygalny | | 3 | 8% | | irytujący | | 2 | 5% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Czy wolałbyś mieć maszynkę do rozstrzygania K, czy do rozstrzygania NP? |
| | K | | 24 | 63% | | NP | | 5 | 13% | | Żadnej | | 7 | 18% | | Zależy, która by mi bardziej pasowała do garażu | | 0 | 0% | | A mogę dostać równowartość w eurogąbkach? | | 2 | 5% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Rosjanie
wymyślili maszynę, która, łącząc się z continuum równoległych
wszechświatów, rozstrzyga K w czasie liniowym. Czemu to przeczy? |
| | Twierdzeniu Cooka | | 4 | 11% | | Tezie Churcha | | 4 | 11% | | Dowodowi nierozstrzygalności K | | 20 | 53% | | Podstawowym zasadom dyplomacji | | 4 | 11% | | Prawom fizyki | | 6 | 16% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Pan
Teodor ma minimalny niedeterministyczny automat, który rozpoznaje język
opisywany przez wyrażenie a*+b*+c* . Ile stanów ma ten automat? |
| | 1 | | 3 | 8% | | 2 | | 0 | 0% | | 3 | | 10 | 26% | | 4 | | 10 | 26% | | 5 | | 10 | 26% | | 6 | | 2 | 5% | | n | | 0 | 0% | | n+1 | | 0 | 0% | | 3n | | 3 | 8% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
Co wiadomo? Wybierz pierwsze prawdziwe zdanie. |
| | P jest różne od NP | | 4 | 11% | | P jest różne od PSPACE | | 9 | 24% | | P jest różne od EXPTIME | | 19 | 50% | | P jest różne od EXPSPACE | | 2 | 5% | | P jest różne od klasy wszystkich problemów rozstrzygalnych | | 4 | 11% |
People may select more than one checkbox, so percentages may add up to more than 100%. |
