Pytania otagowane jako reductions

Redukcja polega na przekształceniu jednego problemu w inny. Przykładem zastosowania redukcji byłoby pokazanie, czy problem P jest nierozstrzygalny. Można to osiągnąć poprzez przekształcenie lub wykonanie redukcji problemu decyzyjnego w problem nierozstrzygalny. Jeśli można to osiągnąć, wykazaliśmy, że problem P jest nierozstrzygalny. $P$

Poprawiasz ogólną redukcję Cooka dla Clique do SAT?

Jestem zainteresowany zredukowaniem kliki do SAT bez powiększania instancji.kkk Klika jest w NP, więc można ją zredukować do SAT za pomocą przestrzeni logarytmicznej. Prosta redukcja podręcznika Garey / Johnson wysadza instancję do sześciennej wielkości. Jednak Klika jest w P dla każdego ustalonego k, więc „powinna” być skuteczna redukcja przynajmniej dla …

10 cc.complexity-theory sat reductions clique

Redukcja trudnych problemów do modeli fizycznych

Szukam przykładów trudnych problemów (w NP lub trudniejszych) z informatyki, które można sprowadzić do modeli procesów fizycznych. Na przykład max-2-sat można zredukować do minimalizacji energii w modelu Isinga. Chciałbym znaleźć więcej przykładów tego rodzaju redukcji.

10 cc.complexity-theory reductions physics formal-modeling

Dowodu złożoności Kołmogorowa nie można obliczyć przy użyciu redukcji

Szukam dowodu, że złożoności Kołmogorowa nie da się obliczyć, stosując redukcję z innego problemu nieobliczalnego. Powszechnym dowodem jest formalizacja paradoksu Berry'ego, a nie redukcja, ale powinien istnieć dowód poprzez redukcję z czegoś takiego jak problem zatrzymania lub problem korespondencji z pocztą.

9 computability reductions kolmogorov-complexity

Jakieś sformułowania SAT / SMT VRP / VRPTW (TSP, Job-Shop-Scheduling)?

zastanawiam się, czy są jakieś podejścia do formułowania problemu trasy pojazdu z systemem Windows-Time ( VRPTW ) (jako problemem decyzyjnym) jako instancji SAT / SMT? (alternatywnie: TSP) Na przykład: „Czy istnieje prawidłowe rozwiązanie odwiedzające wszystkich klientów w ich ramach czasowych przy n = 10 pojazdach?” Ten problem decyzyjny może być …

9 ds.algorithms reference-request sat reductions tsp

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.