Pontus
  • Member for 5 years, 5 months
  • Last seen more than 1 year ago
Can a subset of an NP-complete problem be in P?
10 votes

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 ...

View answer
What is the relation between EXPTIME and NP HARD complexity classes?
9 votes

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, ...

View answer
Any problem solved by a finite automaton is in P
8 votes

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.

View answer
Must reductions be injective?
Accepted answer
5 votes

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
Given a prime power, is it possible to efficiently compute the prime
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
Bounds in NP-completeness proofs
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
Karp hardness of directed monochromatic triangle problem
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
How can I develop a pseudo-polynomial time algorithm for a non-integer problem?
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
Response time of scheduling a DAG where each vertex is a task
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
Finding suitable NP-complete problem to reduce to my problem
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 $\...

View answer
Is the set of all possible finite alphabets uncountable?
1 votes

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. ...

View answer
Where have I gone wrong in "proving" this big-O identity?
0 votes

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}$.

View answer
Is P the set of all algorithms whose run-time is $O\left( n^{ O \left( 1 \right) }\right)$?
0 votes

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 ...

View answer