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).
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-232218 |
| Date | January 2018 |
| Creators | Gedin, Emanuel |
| Publisher | KTH, Teoretisk datalogi, TCS |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2018:418 |
Page generated in 0.0015 seconds