Question: NP Complete (Circuits)

[timbr...@hotmail.com]

I have developed a program which generates a large random logic
operator (actually a neural network which generates this operator).
This is a feedback driven system; there is no external input to the
system apart from the initial data insertion. The entire system is
cyclic; the output of any given neuron (including those which display
the results) is fed back into the system.

My question is this: With having an exact diagram of the operator and
the output states listed, is determining the state of the system which
creates that output an NP Complete class problem?

[Jose Juan Mendoza Rodriguez]

Hello,

C. H. Papadimitriou, in his book 'Computational Complexity',
in chapter 10, makes a brief comment about "the problem of finding
stable states in neural networks in the Hopfield model". He says
that it's equivalent to a problem he's just described called
HAPPYNET, and this one is in the class TFNP (total relations whose
witness can be computed in nondeterministic polynomial time), and
it has no known polynomial-time algorithm. He also gives some
references:

N. Megiddo and C. H. Papadimitriou, "On total functions, existence
theorems, and computational complexity," Theor. Comp. Sci., 81,
pp. 317-324, 1991.

D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis, "How easy is
local search?" Proc. 26th IEEE Symp. on the Foundations of Computer
Science, pp. 39-42, 1985; also, J. CSS, 37, pp. 79-100, 1988.

C. H. Papadimitriou, A. A. Schäffer, and M. Yannakakis, "On the
complexity of local search," Proc. 22nd ACM Symp. on the Theory of
Computing, pp. 838-445 [sic], 1990.

Regards.
Jose Juan Mendoza Rodriguez

let me=josejuanmr in
let privacy=iespana in
let net=es in
m...@privacy.net