Sökning: "Emanuel Gedin"

Hittade 1 uppsats innehållade orden Emanuel Gedin.

  1. 1. Hardness of showing hardness of the minimum circuit size problem

    Master-uppsats, KTH/Teoretisk datalogi, TCS

    Författare :Emanuel Gedin; [2018]
    Nyckelord :computer science; theoretical computer science; complexity theory; minimum circuit size problem;

    Sammanfattning : 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. LÄS MER