The ARNN model relativises \(\mathrm{P}=\mathrm{NP}\) and \(\mathrm{P}\neq \mathrm{NP}\)

DOI10.1016/j.tcs.2013.05.022zbMath1296.68059OpenAlexW1626207893MaRDI QIDQ391177

Raimundo Leong, Costa, José Félix

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.05.022

zbMATH Keywords

dynamical systemsanalog recurrent neural nets (ARNN)cost of an oraclenon-deterministic neural netsoracle Turing machinepositive relativisation of \(\mathrm{P}=\mathrm{NP}\)simulation of a real weighted neural net

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A Survey on Analog Models of Computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Physical oracles: the Turing machine and the Wheatstone bridge
• Walter Pitts and ``A logical calculus
• Analog computation via neural networks
• On the computational power of neural nets
• The dynamic universality of sigmoidal neural networks
• Why there is no such discipline as hypercomputation
• The impact of models of a physical oracle on computational power
• Axiomatizing physical experiments as oracles to algorithms
• Limits to measurement in experiments governed by algorithms
• On the Power of Threshold Measurements as Oracles
• A logical calculus of the ideas immanent in nervous activity