Zastanawiam się, czy istnieje algorytm wielomianowy dla „2-SAT z relacjami XOR”. Zarówno 2-SAT, jak i XOR-SAT są w P, ale czy jest to kombinacja? Przykładowe dane wejściowe: Część 2-SAT: (a or !b) and (b or c) and (b or d) Część XOR: (a xor b xor c xor 1) and (b xor c xor d) Innymi słowy,...
Czy istnienie nierozwiązywalnych problemów natychmiast implikuje nieprzewidywalność układów fizycznych? Rozważmy problem zatrzymania, najpierw konstruujemy fizyczny UTM, powiedzmy, używając zwykłej konstrukcji opartej na obwodach. Wtedy nie może istnieć rozstrzygalna teoria fizyczna, która mogłaby...
Czy istnieje sposób na obliczenie wielkości maksymalnego dopasowania na nieważonym grafie dwustronnym bardziej efektywnie (np. Szybciej) niż obliczenie maksymalnego dopasowania? Jest to dalekie ujęcie, ale często interesującym problemem jest unikanie takich niepotrzebnych obliczeń....
Obecnie uczęszczam na kurs programowania równoległego na moim uniwersytecie, a ostatnio zaczęliśmy rozmawiać o koncepcji monitora. Chociaż rozumiem potrzebę wzajemnego wykluczenia, nie rozumiem, dlaczego miałbym do tego używać monitora. Jak rozumiem, monitor gwarantuje, że dokładnie jeden proces...
Algorytm Brzozowskiego można rozszerzyć na automaty Moore'a, ale jego złożoność czasowa jest generalnie wykładnicza. Czy istnieje jakiś inny algorytm minimalizacji automatów Moore? Jakie są czasy działania tych algorytmów, jeśli takie
Zamknięte . To pytanie jest oparte na opiniach . Obecnie nie przyjmuje odpowiedzi. Chcesz poprawić to pytanie? Zaktualizuj pytanie, aby można było na nie odpowiedzieć faktami i cytatami, edytując ten post . Zamknięte 4 lata temu . Jestem frajerem...
Zoo Złożoności definiuje jako klasę problemów decyzyjnych rozwiązywanych przez deterministyczną maszynę Turinga w czasie liniowym.L IN.LINLIN L IN.⊆ P.LIN⊆PLIN \subseteq P Ponieważ HORN-SAT można rozwiązać w (jak wskazano w algorytmach czasu liniowego do testowania spełniania formuł róg zdań...
Zastanawiałem się, dlaczego taśma / taśmy nie są częścią formalnej definicji maszyny Turinga. Rozważmy na przykład formalną definicję maszyny Turinga na stronie Wikipedii . Definicja, po Hopcroft i Ullman, obejmuje: skończony zestaw stanów , alfabet taśmy Γ , pusty symbol b ∈ Γ , stan początkowy q...
Próbuję uzyskać ogólny obraz znaczenia najmniej ustalonego punktu (LFP) w analizie programu. Na przykład abstrakcyjna interpretacja wydaje się wykorzystywać istnienie LFP. Wiele prac badawczych na temat analizy programów również koncentruje się w dużej mierze na znalezieniu najmniej ustalonego...
W przypadku problemów związanych z satysfakcją z ograniczeń heurystykę można wykorzystać w celu poprawy wydajności solvera z funkcją Bactracking. Trzy najczęściej podawane heurystyki dla prostych solverów do cofania to: Minimalna pozostała wartość (ile wartości jest nadal poprawnych dla tej...
SSSdddSSS∀x∈S, d∤x∀x∈S, d∤x\forall x \in S,\ d \nmid x Oznacz n=|S|n=|S|n = |S|i C=max(S)C=max(S)C = \max(S) . Rozważ funkcję F(x)=F(x)=F(x) = najmniejsza liczba pierwsza niepodzieląca xxx . Łatwo zauważyć, że F(x)≤logxF(x)≤logxF(x) \leq \log x . I przez zestaw SSS , niech F(S)=F(S)=F(S) =...
Kodeks Hash 2015 Okrągły testowania Google ( oświadczenie problemem ) poprosił o następującym problemem: dane wejściowe: siatka z zaznaczonymi kwadratami, próg , maksymalny obszarT ∈ N A ∈ NM.M.MT.∈ N.T.∈N.T \in \mathbb{N}A ∈ NZA∈N.A \in \mathbb{N} Wydajność: największa powierzchnia całkowita...
Próbując zrozumieć związki między kodowaniem Huffmana, kodowaniem arytmetycznym i kodowaniem zakresu, zacząłem myśleć o niedociągnięciach kodowania Huffmana związanych z problemem częściowego upakowania bitów . To znaczy, załóżmy, że masz 240 możliwych wartości dla symbolu i potrzebujesz zakodować...
Biorąc pod uwagę podzbiór iloczynu kartezjańskiego dwóch skończonych zestawów, chciałbym znaleźć jego minimalną osłonę przez zestawy, które same są produktami kartezjańskimi.I×JI×JI \times J Na przykład, biorąc pod uwagę iloczyn między i , mogę obserwować podzbiór i spróbuj pokryć go minimalną...
Algorytm Shora jest często używany jako argument. Może rozwiązać problem faktoryzacji szybciej niż jakikolwiek znany algorytm dla klasycznych komputerów. Jednak nie mamy dowodu, że klasyczne komputery nie mogą również efektywnie uwzględniać liczb całkowitych. Czy istnieje jakiś faktyczny dowód, że...
Chcę wyrazić następujące ograniczenie w całkowitym programie liniowym: y= { 01jeśli x = 0jeśli x ≠ 0.y={0if x=01if x≠0.y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases} Mam już zmienne całkowite i obiecuję, że . Jak mogę wyrazić powyższe ograniczenie w formie odpowiedniej...
Odpowiedź na Programmers.SE charakteryzuje esej Cook ( Przedmioty nie są ADTS ) wypowiedź Obiekty zachowują się jak funkcja charakterystyczna względem wartości typu, a nie jak algebra. Obiekty używają abstrakcji proceduralnej zamiast abstrakcji typu ADT zwykle mają unikalną implementację w...
Usiłuję zrozumieć cel uniwersalnej i egzystencjalnej kwantyfikacji typów. Bawię się pisząc zabawkowy język na podstawie rachunku konstrukcji . Czytałem o Morte i Henku, aby pomóc mi lepiej zrozumieć. Nie rozumiem, dlaczego CoC ma zarówno lambda, jak i całkowitą
Jako zabawny projekt pracowałem nad implementacją C # Richarda Korfa - Znalezienie optymalnych rozwiązań dla kostki Rubika przy użyciu baz danych wzorców. https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf Właściwie to działa, staram się tylko ulepszyć swoje...
Tytuł mówi wszystko, ale jestem ciekawy, ponieważ nie jest oczywiste, jak to się stało, że nazwano go „Isabelle”. Czy to imię pochodzi od osoby? Niektórych wyszukiwań w Google nie mogłem się