The ARNN model relativises P=NP and P NP

DOI10.1016/J.TCS.2013.05.022MaRDI QIDQ391177zbMATH OpenOpenAlexFDO

Authors Raimundo Leong, José Félix Costa

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

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

Mathematics Subject Classification ID

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

Recommendations

• Stochastic analog networks and computational complexity
• Relativizations of the P=?NP question over the reals (and other ordered rings)
• scientific article; zbMATH DE number 1260390
• On relativizations of the P =? NP question for several structures
• Oracles and relativizations of the P =? NP question for several structures

Cites work

• A logical calculus of the ideas immanent in nervous activity
• Analog computation via neural networks
• Axiomatizing physical experiments as oracles to algorithms
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 51537 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 1260390 (Why is no real title available?)
• scientific article; zbMATH DE number 953043 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• Limits to measurement in experiments governed by algorithms
• On the computational power of neural nets
• On the Power of Threshold Measurements as Oracles
• Physical oracles: the Turing machine and the Wheatstone bridge
• The dynamic universality of sigmoidal neural networks
• The impact of models of a physical oracle on computational power
• Walter Pitts and ``A logical calculus
• Why there is no such discipline as hypercomputation

Cited in

(4)

• Stochastic analog networks and computational complexity
• scientific article; zbMATH DE number 1728659 (Why is no real title available?)
• A Survey on Analog Models of Computation
• \(\text{NP}\not={co}\)-NP and models of arithmetic

This page was built for publication: The ARNN model relativises \(\mathrm{P}=\mathrm{NP}\) and \(\mathrm{P}\neq \mathrm{NP}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q391177)