Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with NP hard problems:
TR18-080 | 6th March 2018
Moritz Gobbert

Edge Hop: A Framework to Show NP-Hardness of Combinatorial Games

The topic of this paper is a game on graphs called Edge Hop. The game's goal is to move a marked token from a specific starting node to a specific target node. Further, there are other tokens on some nodes which can be moved by the player under suitable conditions. ... more >>>

TR20-183 | 6th December 2020
Rahul Ilango

Constant Depth Formula and Partial Function Versions of MCSP are Hard

Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions.

While ... more >>>

ISSN 1433-8092 | Imprint