This is an area that admittedly I've always found subtle about CS and occasionally trips me up, and clearly others. recently on tcs.se a user asked an apparently innocuous question about N-Queens being NP hard, But it got downvoted there & goes unanswered because the audience felt it was poorly phrased.
The issue seems to be that some questions in CS have to be phrased as decision problems to measure their complexity, and it is not always obvious how to do that. also other questions are studied from the POV(point of view) of computing a function with integer or string inputs and outputs, in which case eg their time or space complexity can be studied. for some NP complete problems e.g. SAT its proven that the decision problem (e.g. determining whether an answer exists) is roughly equivalent in time/space complexity to solving the function problem (finding a satisfying assignment), but of course that's not always the case.
Moreover much of CS theory is focused on NP complete problems [esp that presented to undergraduates in textbooks], which are nec. decision problems, which might lead to a mistaken impression that other types of problem formats are not as central to the theory. Also NP complete is sometimes shown in a hierarchy that includes other complexity classes such as PSpace which can be used to measure function complexity in addition to decision complexity.
Think that the N-Queens example question & related comments also shows that a bunch of related questions about the same problem in this case N-Queens can vary widely/dramatically in their complexity depending on slight variations of the phrasing. e.g. in this case:
- Is there a solution to the N-Queens problem on a $n \times n$ chessboard? this problem turns out to have O(1) time complexity— the answer is always Y.
- What is the complexity of finding a solution to the N-Queens problem given $n$ as the input referring to a square $n \times n$ chessboard? as that question notes in comments by Peter Shor, an advanced and subtle thm from CS called "mahaney's" thm applies because it might refer to a "sparse input". also JeffE found a paper that says its in P.
- There is an NP complete or NP hard version of this problem if the squares are irregularly specified as the input. i.e. some kind of input that specifies the square allowed/unallowed locations (haven't looked up the details).
While advanced theorists may find all this verging on trivial, feel its a legitimate area of focus which sometimes gets glossed over in theoretical treatments. my question
Is there a reference somewhere that points/sorts out these kinds of subtleties/difficulties in formulating CS problems?
It would be helpful if it also talks about how the issue relates to the complexity hierarchy. know that this is covered in some textbooks, but even then haven't seen a nice concise discussion of that and wonder if anyone has a favorite ref for this type of issue. (suppose Garey and Johnson might have some discussion of this although don't have a copy close to check.)
Am not specifically focused on the N-Queens problem with this question, but an answer that sketches out the distinctions wrt N-Queens might be helpful. [eg an expanded explanation of Shor's comment how Mahaneys thm applies, the irregular board construction input format, etc]
fyi here are two other example problems Ive noticed that can vary widely in complexity depending on various restrictions on the input
 Finding whether a regular expression is equivalent to all strings over the alphabet. with squaring this was shown to be in ExpSpace by Stockmeyer/Meyer, but restrictions on length lead to it to being in NP complete or P. see e.g. Chee Yap, Intro to Complexity classes, ch5 on complete problems.