| Autor: |
Sälzer, Marco, Lange, Martin |
| Rok vydání: |
2021 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1007/978-3-030-89716-1_10 |
| Popis: |
We investigate the complexity of the reachability problem for (deep) neural networks: does it compute valid output given some valid input? It was recently claimed that the problem is NP-complete for general neural networks and conjunctive input/output specifications. We repair some flaws in the original upper and lower bound proofs. We then show that NP-hardness already holds for restricted classes of simple specifications and neural networks with just one layer, as well as neural networks with minimal requirements on the occurring parameters. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
