Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Hardness of showing hardness of the minimum circuit size problem
KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
2018 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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).

Abstract [sv]

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).

Place, publisher, year, edition, pages
2018. , p. 37
Series
TRITA-EECS-EX ; 2018:418
Keywords [en]
computer science, theoretical computer science, complexity theory, minimum circuit size problem
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-232218OAI: oai:DiVA.org:kth-232218DiVA, id: diva2:1233107
Subject / course
Computer Science
Educational program
Master of Science in Engineering -Engineering Physics
Presentation
2018-06-27, Room 4523, Lindstedtsvägen 5, Stockholm, 13:15 (English)
Supervisors
Examiners
Available from: 2018-08-31 Created: 2018-07-16 Last updated: 2018-08-31Bibliographically approved

Open Access in DiVA

fulltext(561 kB)29 downloads
File information
File name FULLTEXT01.pdfFile size 561 kBChecksum SHA-512
9b1ec9263c38bcfb3117bf620db0933e7f1aae0a8344c4d3cc743a223ef607e90b5726ebad296a3de01ff2c901c0be84786b08326db41f5dd945586c11229199
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Gedin, Emanuel
By organisation
Theoretical Computer Science, TCS
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 29 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 258 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf