4 ms·
Wouldn't it be more accurate to state that it's NP-complete? In the first step of the proof they show that SR-Dec is in NP.
by enricozb 4y ago
Wouldn't it be more accurate to state that it's NP-complete? In the first step of the proof they show that SR-Dec is in NP.
- deleted 4y ago[deleted]
- red_trumpet 4y agoI would say it's stylistically questionable to include the proof that it's in NP under the proof of NP-hardness. They could have written it in a paragraph before. However it could still be true that this result was known beforehand (and judging by the length of the proof, it doesnt seem too difficult). So their main result would still be the NP-hardness, which justifies the name of the paper.