Return to search

Hardness of showing hardness of the minimum circuit size problem

The problem of finding the smallest size of a circuit that computes a given boolean function, usually referred to as the minimum circuit size problem (MCSP), has been studied for many years but it is still unknown whether or not the problem is NP-hard. With this in mind we study properties of potential reductions to this problem. The reductions in focus are local natural reductions which has been common in other well-known proofs of NP-hardness. We present a generalized method that shows the existence of an algorithm solving any problem which has a local natural reduction to MCSP. In particular we show that if the decision problem of distinguishing satisfiable 3-SAT instances from those where at most 7/8 + o(1) of the clauses can be satisfied has a reduction to MCSP where any arbitrary bit of the output can be computed in O(n1 - ε) time for any ε > 0 then k-SAT can be solved by a circuit of depth 3 and size 2o(n). / Problemet att finna den minsta storleken på en krets som beräknar en given boolesk funktion, ofta kallat minimum circuit size problem (MCSP), har studerats i många år men det är fortfarande okänt om problemet är NP-svårt eller inte. Med detta i åtankte studerar vi egenskaper hos potentiella reduktioner till det här problemet. Vi fokuserar på naturliga lokala reduktioner som är vanliga i många bevis av NP-svårighet. Vi presenterar en method som visar att det finns en algorithm för att lösa varje problem som har en lokal naturlig reduktion till MCSP. Vi visar att om beslutsproblemet att skilja satisfierbara instanser av 3-SAT från de där som mest 7/8 + o(1) av klausulerna går att satisfiera har en reduktion till MCSP där en godtycklig bit av utdata kan beräknas i O(n1 - ε) tid för varje ε > 0 då kan k-SAT lösas av en krets med djup 3 och storlek 2o(n).

Identiferoai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-232218
Date January 2018
CreatorsGedin, Emanuel
PublisherKTH, Teoretisk datalogi, TCS
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageEnglish
TypeStudent thesis, info:eu-repo/semantics/bachelorThesis, text
Formatapplication/pdf
Rightsinfo:eu-repo/semantics/openAccess
RelationTRITA-EECS-EX ; 2018:418

Page generated in 0.0022 seconds