May 27: M. Hermann, Complexity of Counting the Hilbert Basis of a Linear Diophantine System


Subject: May 27: M. Hermann, Complexity of Counting the Hilbert Basis of a Linear Diophantine System
From: Helmut Veith (kgs-owner@dbai.tuwien.ac.at)
Date: Fri May 21 1999 - 19:31:55 MET DST


Lecture Announcement

Miki Hermann
=======================
LORIA, Nancy

May 27, 17:00

On the Complexity of Counting the Hilbert Basis of a Linear Diophantine System
------------------------------------------------------------------------------

Abstract:

   We investigate the computational complexity of counting the Hilbert
   basis of a homogeneous system of linear Diophantine equations. We
   establish lower and upper bounds on the complexity of this problem
   by showing that counting the Hilbert basis is #P-hard and belongs
   to the class #NP. Moreover, we investigate the complexity of
   variants obtained by restricting the number of occurrences of the
   variables in the system.
 
Bemerkung: Der Vortrag wird in deutscher Sprache gehalten, soferne
kein fremdsprachigen Hoerer anwesend sind.

PLACE:

Seminarraum SEM 181A, Institut fuer Informationssysteme,
Paniglgasse 16, 1. Stock, 1040 Wien.

------------------------
Kurt-Goedel-Gesellschaft
Technische Universitaet Wien
Institut fuer Computersprachen E185.2
Resselgasse 3/1, A-1040 Wien



This archive was generated by hypermail 2b25 : Thu Apr 06 2000 - 16:19:21 MET DST