Definicja: Redukcja karp Język jest karpem redukowalnym do języka jeśli istnieje funkcja obliczalna w czasie wielomianowym tak, że dla każdego , wtedy i tylko wtedy, .AAABBBf:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f:\{0,1\}^*\rightarrow\{0,1\}^*xxxx∈Ax∈Ax\in Af(x)∈Bf(x)∈Bf(x)\in B Definicja: Redukcja...
Mam ten bardzo prosty „dowód” na NP = CoNP i myślę, że gdzieś coś zrobiłem źle, ale nie mogę znaleźć, co jest nie tak. Czy ktoś może mi pomóc? Niech A będzie pewnym problemem w NP, i niech M będzie decydującym dla A. Niech B będzie dopełnieniem, tj. B jest w CoNP. Ponieważ M jest decydującym,...
Ostatnie pytanie egzaminacyjne brzmiało następująco: jest nieskończonym zestawem rekurencyjnie wyliczalnym. Wykazać, że A ma nieskończony rekurencyjny podzbiór.ZAAAZAAA Niech jest nieskończony rekurencyjne podzbiór A . Czy C musi mieć podzbiór, którego nie można wyliczyć...