Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Wednesday, April 30, 2014, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Antonis Thomas
In this talk, the following problem is considered: Given a Boolean Circuit with n inputs and n outputs, decide if it represents a Unique Sink Orientation (USO). We prove this problem to be coNP-complete. However, the situation is more involved for Acyclic USOs (AUSO). While it remains coNP-hard to recognize an AUSO, we leave open the problem of inclusion that there exist cyclic USOs with superpolynomially long cycles.
Automatic MiSe System Software Version 1.4803M | admin login