Vi anser att tillfredsställande problem för kretsar av begränsad storlek och / eller djup. Säg att en algoritm som löser en Boolesk satisfiability problem på n variabler förbättras if det tar tid O(2 cn ) för vissa konstant c < 1, dvs. Om det är exponentiellt bättre än en brute force sökning. Vi visar en förbättrad algoritm för tillfredsställande problem för kretsar av konstant djup och linjär storlek. Om förbättrade övre gränser inte är möjliga för en variant där storleken är något mer än linjär eller djupet växer, kan vi ge bevis om problemets hårdhet? (observera till författare: Har vi verkligen diskuterat denna fråga mer ingående i tidningen? Det här kanske borde omformuleras.) För varje d och c ger vi en randomiserad algoritm som löser tillfredsställande problem för djup-d-kretsar med n-variabler och som mest cn-portar i tid 2 (1−δ)n där δ ≥1/O(c −2 c), och konstanten i big-Oh beror endast på d. Algoritmen kan justeras för användning med Grovers algoritm för att uppnå en körtid på 2 1−δ 2 n på en kvantdator.
Den första är en algoritm på grund av Calabro, Impagliazzo och Paturi REF som har en körtid av formen c n, c < 2 för tillfredsställelse av konstant djup Booleska kretsar av linjär storlek.
The Complexity of Satisfiability of Small Depth Circuits
{'venue': 'IWPEC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}