Questions tagged [decision-problem]

A question in some formal system with a yes-or-no answer.

Filter by
Sorted by
Tagged with
-2 votes
1 answer
19 views

How do you show that Cosmic Kite Problem is NP complete?

A "cosmic kite" of size k consists of a clique of k nodes with a path of k nodes that unfolds from one of the nodes in the clique. Cosmic Kite as decision problem Input: a graph G = (V, E) ...
Nicolò Bonacorsi's user avatar
1 vote
1 answer
44 views

Does the Subset Product Problem remain NP-complete if repetition in S is not allowed?

Just curioius, I wanted to know when $S$ ={set of divisors of N} and we're given $N$ a target product. Our goal is to decide if a combination in $S$ has product equal to N. Does the problem remain NP-...
The T's user avatar
  • 319
2 votes
1 answer
94 views

Determining whether two special variants of knapsack have the same optimal value

Given two unbounded knapsack instances, $K_1 = (W_1, weights, values), K_2 = (W_2, weights, values)$, where $W_1 \ne W_2$, what is the complexity of determining $v(K_1) = v(K_2)$ where $v$ returns the ...
rossignol's user avatar
1 vote
1 answer
36 views

Decidability terms clarification

I just need some clarification regarding the different terms we use in theoretical computer science, especially regarding decidability. Decidable: A language $L$ (a set of strings) is decidable if ...
Just Curious's user avatar
0 votes
0 answers
29 views

What does a problem not in $NSPACE(cn / \log(n))$ tell me?

I have the following two resuts taken from the book "The Classical Decision Problem". How does Corollary 6.3.28 follow? How can I derive PSPACE-hardness from non-membership in $NSPACE(cn / \...
user1868607's user avatar
  • 2,194
1 vote
0 answers
24 views

Stable Flow Problem with one sided preferences

I'm currently working on a problem to come up with ideas to solve a stable flow problem but unlike the traditional stable flow problem where every node has preferences on its incoming and outgoing ...
Finn's user avatar
  • 11
1 vote
1 answer
114 views

Reduce CNF-SAT to decision problem

Given CNF-SAT reduce it to the following decision problem: Given n items, m groups (and for each group a set of items) and a ...
popcorn's user avatar
  • 183
0 votes
1 answer
13 views

Transform OTM for Problem π to DTM ∈ DSPACE(n)

Given an Oracle Turing machine ($OTM$) that solves Problem π in max. 2n space, so $O(n)$ space and $O(n^2)$ time. Is there a DTM that can solve $π$ in $O(n)$ space if time doesn't matter? (The length ...
Theorynoob's user avatar
5 votes
3 answers
1k views

Small doubt concerning cardinality of set of problems and algorithms?

I write this question because my professor in Algorithm Analysis briefly mentioned some property related to the countability/uncountability of the set of strings/problems/algorithms and the consequent ...
Sho's user avatar
  • 159
0 votes
0 answers
35 views

Greedy algorithm for trading cryptocurrencies with perfect price information

Assume the following hypothetic scenario: You know the values $v_1^0, \ldots, v_n^0$ of $n$ cryptocurrencies. You know the values this currencies will have for the following $m$ days; this is, $v_0^1,...
lafinur's user avatar
  • 181
1 vote
0 answers
31 views

Complexity class of a problem asking for a chance of receiving an item

I have asked a question on math.SE about if there is a way to do it better than by brute force, but this time I am interested in the complexity of the problem itself. I will repeat the problem, with a ...
rus9384's user avatar
  • 1,632
0 votes
0 answers
34 views

An Example of the Conjuction of Two NP-Complete Decision Problems Being Polynomial Time Solvable [duplicate]

Firstly, we define A and B as two decision problems with the same set of inputs. Define a new decision problem "A AND B" as follows: The input to "A AND B" is any valid input x for ...
Oluchi A's user avatar
0 votes
0 answers
135 views

Non-deterministic Turing machine that decides the language $L = \{0^{n^2} | n \geq 1\}$

I was trying to figure out how can I construct a non-deterministic Turing machine that decides the language $L = \{0^{n^2} | n \geq 1\}$ I looked at some of the proposed solutions here : Turing ...
Yarin's user avatar
  • 275
0 votes
0 answers
30 views

How to formulate "The general Sudoku problem is in P" formally and rigorously? How to calculate then the input size?

We consider a partially filled starting grid, where $n^2$ is the side size of the grid, $m$ is the number of non-empty initial squares, $f$ is the function that places randomly initially the integers ...
someone's user avatar
  • 11
0 votes
1 answer
30 views

Is « Does exist at least one function $u$ such that $f(u(0)) \ne g(u(0))$? » an NP problem? or a P problem?

$f$ and $g$ being known functions. We suppose that the problem is solvable. To me, for the moment, this question, if a decision problem it is or can be, is more an NP rather than a P problem, because ...
someone's user avatar
  • 11
2 votes
1 answer
58 views

Subset sum reducible to barter economy problem?

I was given the following problem called the barter economy problem: Given a set of $n$ people $\{p_1, \ldots, p_n\}$ and a set of $m$ distinct objects $\{a_1, \ldots, a_m\}$, where each object $a_j$ ...
redbull_nowings's user avatar
1 vote
1 answer
87 views

If the Navier-Stokes equations problem is a computable problem, for example a set/language called "L", what are the elements of L?

First, can the Navier-Stokes problem be a formal computable one? like a P problem? Then, how to define the corresponding language? Would it only be the set of equations, or something else? Then, could ...
someone's user avatar
  • 11
0 votes
0 answers
24 views

Greedy algorithm for minimising the number of encountered obstacles from multiple start points to single endpoint in a grid

I am given a $N$ x $M$ sized grid and $K$ start points $S = (s_1, s_2, .. s_k)$ where each $s_k = (x_k,y_k)$ representing the position on the grid. I am also given a single endpoint $(x_{end}, y_{end})...
calveeen's user avatar
  • 141
2 votes
0 answers
23 views

Stålmarck's method, can triplets be dropped once they triggered equivalences

In Sheeran, Mary, and Gunnar Stålmarck: A tutorial on Stålmarck’s proof procedure for propositional logic there is an example application of the method to...
user3128's user avatar
1 vote
1 answer
57 views

Do function problems have an interpretation in terms of formal languages?

In computational complexity theory, decision problems are typically defined as formal languages, and complexity classes are defined as the sets of the formal languages that can be parsed by machines ...
user avatar
19 votes
2 answers
4k views

Why are computability problems always written in full caps?

Maybe this is an odd question. It has always bugged me that computability problems are written in all caps, and in such an "awkward" way. SAT, 3-SAT, COLORING, 3-COLORING, PARTITION, CLIQUE, ...
Julian W.'s user avatar
  • 191
0 votes
1 answer
33 views

If I want to prove that a problem is in NP, can the vertifier use exponential space?

I want to prove that a problem is in NP. I have a witness (of polynomial size), and a verifier that runs in polynomial time. However, this verifier uses exponential space, becuase it has to generate ...
user606273's user avatar
0 votes
3 answers
101 views

Does exist an algorithm that decides whether a program halts or not as its timeout approaches to infinity?

By an algorithm $A(p, t)$ attempting to decide whether the program $p$ halts or not by running the program for $t$ seconds (the timeout) and trying to prove that it doesn't halt at the same time, can ...
sbh's user avatar
  • 51
-1 votes
1 answer
40 views

Schaefer's dichotomy theorem and limits on the formula length

Schaefer's dichotomy theorem ensures than when a constraint satisfiability problem satisfies certain conditions, the problem is either in $\mathsf P$ or is $\mathsf{NP}$-hard. Suppose the following ...
rus9384's user avatar
  • 1,632
2 votes
1 answer
117 views

On hardness of finding dominating sets in triangle-free regular graphs

A $k$-regular graph is one in which every vertex has degree k. A triangle-free graph is one in which any three vertices do not form a triangle. A dominating set $D$ of a graph $G$ is a set of vertices ...
Ankit Gayen's user avatar
-2 votes
2 answers
117 views

Can we tell if we can tell if an algorithm halts or not?

We proved that, there exist no algorithm so it can tell us if an algorithm halts or not (a.k.a. the halting problem is undecidable). But it surely can handle some of those; can we tell which of those ...
sbh's user avatar
  • 51
0 votes
1 answer
74 views

Max Unique Clique in $\Sigma^2_p$

I want to prove that the language $\text{Max-Unique-Clique} = \{<G> | \text{The maximal clique of $G$ is unique}\}$ is in $\Sigma_2^p$ by using the following $\Sigma_2^p$ machine: The machine ...
OriFrid's user avatar
  • 110
2 votes
1 answer
289 views

Constructing equivalent (to a polynomial-time degree) decision problems from function problems

Let's say we're some function problem, $R \subseteq \Sigma^* \times \Sigma^*$, where $\Sigma = \{0, 1\}$ and some oracle $O_R$ that solves $R$. Now, we're given some language, $L \subseteq \Sigma^*$ ...
Andrew Baker's user avatar
0 votes
1 answer
62 views

Minimal Hitting Sets Problem

Let $\mathcal{I} = \{I_0, \ldots, I_{m-1}\}$ a collection of subset of some universe $U$. We want to find a partition $P$ of $\mathcal{I}$ of minimal cardinality such that the intersection of each set ...
matteo_c's user avatar
  • 133
0 votes
0 answers
20 views

Solving a weighted minimum dominating set problem with its unweighted counterpart?

Question Is it possible to find a solution to the weighted minimum dominating set problem, by solving a (related), unweighted minimum dominating set? Elaboration In essence, can one convert a ...
a.t.'s user avatar
  • 123
1 vote
1 answer
76 views

Decision version of optimization problems with polynomial-time approximation algorithms

Given an optimization problem $X$, it is easy to construct a decision problem $Y$, such that there is a two-directional polynomial-time reduction between $X$ and $Y$. Therefore, we can define a class ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
79 views

Why aren't promise problems just decision problems; can't we encode the promised inputs in the alphabet?

I don't really understand why promise problems are classified differently than decision problems. Consider this problem as an example. Given some real number between $0$ and $1$, determine if it ...
Loic Stoic's user avatar
0 votes
1 answer
127 views

Ackermann Decision Problem

I have been studying the Ackermann function, specifically the two-argument Ackermann–Péter version. With the Ackermann function, I developed a problem I call the "Ackermann Decision Problem" ...
CoalLad's user avatar
  • 143
1 vote
1 answer
84 views

Why is 3-co-SAT not in P?

The 3-co-SAT problem consists of deciding whether if a 3CNF formula, has an unsatisfiable assignment of variables, i.e., assignment of variables that evaluates to 0. We know that 3-co-SAT is in coNP, ...
Denizalp's user avatar
0 votes
1 answer
41 views

Is $\overline{A_{TM}}$ co-NP Hard?

I know that $A_{TM}=\{<M,w>|M~is~a~TM~and~M~accepts~w\}$ is NP-Hard: By showing a polynomial time reduction - $A \le_p A_{TM}$: Let $A \in NP$, then there exists a $NTM$ that decides $A$ in ...
Geo's user avatar
  • 47
1 vote
1 answer
67 views

Is the set of instances of PCP, which have a solution, semi-decidable?

My idea was that it is because we can construct a TM M' that simulates a TM M that is to find a solution for a PCP instance. M' accepts if M accepts, rejects if M rejects, and doesn't halt if M does ...
Natalia Markoborodova's user avatar
0 votes
1 answer
45 views

Integer factorization: Why can't we use the test algorhitm to create an algorhitm to decide the factoring decision problem in polynomial time?

I'm reading Nielsen and Chuang. On page 142 the integer factoring decision problem is introduced: The integer factorization problem can be reduced to a decision problem: Given a composite integer m ...
Opinel's user avatar
  • 11
1 vote
1 answer
60 views

The meaning of Tautology and Contradiction in Complexity theory

I recently had this question answered on stack exchange: if X is in NP but Y is not in NP then can X be reduced to Y? The answer proposed a counter example using an element of complexity theory I had ...
bmanicus131's user avatar
0 votes
1 answer
92 views

Show that $\text{BOOL-VAL}$ and $\text{DNF-SAT}$ is decidable in linear time

A boolean expression is valid if it is true for every valuation. The problem $\text{BOOL-VAL}$ asks whether a given boolean expression is valid. As the question suggests I need to show that $\text{...
user avatar
0 votes
1 answer
82 views

if X is in NP but Y is not in NP then can X be reduced to Y?

I have been led to believe that the following statement $X \in NP \land Y \not\in NP \implies X \not\le^m_p Y$ Is True. But I am having difficult proving it. And I'm not even sure it IS true anymore. ...
bmanicus131's user avatar
0 votes
2 answers
127 views

Is a language semi-decidable iff it is reducible to ATM?

Thank you. I see how it makes sense going in the opposite direction but i need help proving that this is true. Below is the definition of ATM. ATM={<M,w>| a TM, M accepts w} The question from my ...
Carrey's user avatar
  • 1
0 votes
0 answers
72 views

Can I find the smallest vertex cover

so this is my question:- If I manage to find a vertex cover which has ....let's say 100 more vertex than the minimum vertex cover. Can I find the minimum vertex cover in polynomial time from this ...
alwayscurious's user avatar
0 votes
1 answer
130 views

MAX-SAT approximation factor

I am stuck on an exercise that ask the approximation factor of a MAX-SAT approximated algorithm generalized from a MAX-3SAT algorithm MAX-3SAT: set every variable with a random value ($0$ or $1$ each ...
Marcus34's user avatar
1 vote
1 answer
333 views

NP-Complete Reduction

Prove the following problem is NP-Complete: The problem gave a directed graph G, and several subsets of vertices of such graph are being specified as T1,T2,....Tn, and the subsects could intersect, ...
Kensh1n's user avatar
  • 13
0 votes
0 answers
25 views

Why is the collection of decision problems closed under set operations?

Most of the proofs of such properties that I see involve informally using algorithms or invoking Turing machines as needed. But it's not clear to me how are we using set operations on instances of ...
user avatar
-3 votes
1 answer
66 views

Given a list of numbers L and a target k, is there a subset of numbers from L whose product is k?

Is there any dynamic way of solving this problem? I would thank any help, I know the Subset sum Problem, but for solving it dynamically u have to create a matrix but here is not posible as the colums ...
SEBASTIAN ROJAS BUENO's user avatar
1 vote
1 answer
45 views

Decision tree to check 2 rectangles

Given two disjoint rectangles $(a,b]\times (c,d]$ and $(e,f]\times (g,h]$ in $\mathbb{R}^2$ how can I check with a decision tree of least depth if a given point $(x,y)$ lies within the union of the ...
treeman8's user avatar
0 votes
1 answer
615 views

Does the halting problem belong to NP class of problems?

On the one hand it does not belong to NP problems because it simply is not solvable and is undecidable and on the other hand it is an NP problem because there are claims that it is NP-hard and ...
Anna's user avatar
  • 1
2 votes
1 answer
72 views

Is there an algorithm for this decision problem that is better than brute-force?

Apologies for the vague title. This decision problem has applications to graph coloring but I have not found a name for it in the literature. I am trying to improve my algorithm for a decision problem....
Brett Schreiber's user avatar
9 votes
2 answers
5k views

Is SAT an existential question?

Some sources state that an algorithm that solves the SAT problem not only needs to decide whether a given existentially-quantified formula is satisfiable or not, but, additionally, in the case where ...
tonik's user avatar
  • 195

1
2 3 4 5
11