Training a 3-node neural network is NP-complete: NP-completeness of exact training on Boolean inputsResearch Paper
Training a classifier asks for parameters that fit observed examples. Even when the data can be classified perfectly, the task of finding suitable parameters can have substantial computational cost. The question here concerns exact training: deciding whether any parameter choice makes zero mistakes on the entire supplied data set. It concerns computation on…