Pytania otagowane jako check-my-proof

1
Liczba cykli hamiltonowskich na wykresie Sierpińskiego
Jestem nowy na tym forum i jestem tylko fizykiem, który robi to, aby utrzymać swój mózg w dobrej formie, więc proszę okaż łaskę, jeśli nie używam najbardziej eleganckiego języka. Proszę również zostawić komentarz, jeśli uważasz, że inne tagi byłyby bardziej odpowiednie. Próbuję rozwiązać ten problem, dla którego muszę obliczyć liczbę …
5
Wada mojego NP = dowód CoNP?
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 …
2
Czy redukcja karp jest identyczna z redukcją Levina
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 Levina Problem wyszukiwania można sprowadzić do Levina do problemu wyszukiwania jeśli istnieje funkcja czasu wielomianowego której Karp redukuje do a …
1
podzbiory nieskończonych zbiorów rekurencyjnych
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ć rekurencyjnie?doCCZAAAdoCC Odpowiedziałem już 1.. W odniesieniu do 2. odpowiedziałem twierdząco i twierdziłem, co następuje. Załóżmy, że wszystkie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.