Essays about: "Emanuel Gedin"

Found 1 essay containing the words Emanuel Gedin.

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

    University essay from KTH/Teoretisk datalogi, TCS

    Author : Emanuel Gedin; [2018]
    Keywords : computer science; theoretical computer science; complexity theory; minimum circuit size problem;

    Abstract : 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. READ MORE