Optical solution for hard on average #P-complete instances (using exponential space for solving instances of the permanent)

Authors: Anter, Amir¹; Dolev, Shlomi²

Source: Natural Computing, Volume 9, Number 4, December 2010 , pp. 891-902(12)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

Optical architectures that use exponential space for solving instances of the (non-necessarily-binary) permanent are presented. This is the first work to specifically focus on such hard on average problems. Two architectures are suggested the first is based on programmable masks, and the second on preprepared fixed number of masks.

Keywords: Optical computing; Permanent; Hard in average

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s11047-009-9168-2

Affiliations: 1: Department of Computer Science, Ben-Gurion University of the Negev, Beer Sheva, Israel 2: Department of Computer Science, Ben-Gurion University of the Negev, Beer Sheva, Israel, Email: dolev@cs.bgu.ac.il

Publication date: 2010-12-01