As I understand your question, yes, this is possible. As an example, consider the (infinitely large) subset of SAT that contains all satisfiable formulae with no negations. This subset is trivially in ...

There are NP-hard problems that are not in EXPTIME and vice versa. This is to be expected as NP-hard is defined by a lower bound and EXPTIME mainly by an upper bound. NP is contained in EXPTIME, ...

Yes, this is true. For every such problem there is a DFA that decides the language, and checking if a word is accepted by a DFA can easily be done in time linear in the length of the word.

The function $f$ does not need to be injective. It would be fine to map every $w \in A$ to the same element $w' \in B$ (and to map every $w \in \Sigma^* \setminus A$ to the same $w'' \in \Sigma^* \... View answer Accepted answer 5 votes Yes, here is a simple approach (there are likely more efficient ones). Let$n$be the number given. Observe that$2 \leq p \leq n$and$1 \leq i \leq \log_2(n)$. For each possible value of$i$in the ... View answer 4 votes Note that you got it wrong in the question. What you have is that if$Y \leq^p_m X$and$Y$is NP-hard, then$X$is also NP-hard. This is true by definition, unconditional on any other lower bounds ... View answer Accepted answer 3 votes All directed graphs can be edge-partitioned into two subgraphs that are acyclic and therefore triangle free. Let$\prec$be any total ordering of the vertices. For each edge$(u, v) \in A$, put it in ... View answer Accepted answer 2 votes Classifying algorithms as pseudo-polynomial time is not really a meaningful concept if there are no numbers (integers) in the instances. Of course, it is up to you to define what parts of the input ... View answer 2 votes A simple upper bound on the response time, for any work-conserving scheduler, is $$\frac{\mathit{vol} - L}{x} + L,$$ where$\mathit{vol}$is the sum of all the execution times and$L$is the sum of ... View answer Accepted answer 2 votes This problem is essentially just a rephrasing of the classic NP-complete problem PARTITION. If you can partition a set$S$of natural numbers into two partitions$S_1$and$S_2$with equal sum, then$\...

Your approach can essentially be summarized as: I define an injection between $\mathbb{N}$ and my set $S$. This injection is not a bijection because some elements of the codomain are left unmapped. ...

Your mistake seems to be in assuming that $a^n \cdot a^m = a^{nm}$. Rather, we have $a^n \cdot a^m = a^{n + m}$.
P is not a set of algorithms, it is a set of languages, where a language is a subset of $\{0, 1\}^*$. In your terminology, the universe of discourse is the power set of $\{0, 1\}^*$ (Russell's paradox ...