Questions tagged [decision-problem]
A question in some formal system with a yes-or-no answer.
564 questions
-1
votes
0
answers
27
views
problem solving skill important? [closed]
I am a software engineering student, start learning by sheet this skill but I found it hard after 1 month and still stack over and over is it normal ?
what is your advice for me
0
votes
0
answers
136
views
Complexity class of $\#\mathrm{P}$-hard counting problem can be reduced to $\#\mathrm{P}$ given its own output for different values
I have a counting problem that famously has evaded being solved by simply counting the elements of a set and somehow seemed to have involved subtraction in an essential way (it is in $\mathrm{GapP}^+$,...
- 133
0
votes
1
answer
83
views
Complexity class of an algorithm for finding the minimal elements of a partially ordered set of exponential size
I have a problem with the following specs:
The input is a permutation of size $n$.
The search space is a poset where the size could be up to $\left(\frac{n}{4}\right)!^2$ (or possibly larger, but I ...
- 133
0
votes
1
answer
70
views
Why formulate P vs NP in terms of binary strings?
Let $L \subset \sigma^*$ be a decision problem. An Algorithim M is a polynomial bounded verifier for $L$, when:
M has a polynomial bounded run time
$M(x,z)$ the output on the the input $x \text{#} z$....
1
vote
1
answer
76
views
Simple Unbounded Multi-Knapsack with Distinct Items Constraint - strongly or weakly NP-c?
Is the following Knapsack problem strongly or weakly NP-hard? We have unbounded knapsacks, meaning we can use each item unlimited number of times.
Given:
$I = \{ w_1, ... w_n \}$ - a set of the ...
0
votes
0
answers
20
views
Is there an generalization of Knuth-Bendix completion to reflexive, transitive relations?
I am interested in the question of deriving decision procedures for formal theories which deal with a set $X$ equipped with a distinguished binary relation $\leq$ that is reflexive and transitive, as ...
0
votes
1
answer
93
views
Comparing Two Adjacency Matrices for Graph Equality
I'm currently working on a project that partially involves graphs. One of the problems I'm tackling is determining whether two given matrices represent the same graph.
So given two different adjacency ...
- 47
4
votes
1
answer
1k
views
How can we even write down a undecidable problem?
From my current understanding, a decision problem is basically another way to specify a formal language, i.e. a subset of all inputs. But I cannot imagine what does a undecidable problem even mean. If ...
- 307
0
votes
0
answers
55
views
If NP=P, what will happen to this planet? [duplicate]
I know that our modern IT infrastructure is based on the assuption that NP!=P, e.g. cryptocurrency, public key cryptography. But if(only if), if NP=P, someone at sometime find that one algorithm could ...
- 101
0
votes
2
answers
135
views
Why are finite sets decidable?
I am currently trying to understand why some finite sets or problems are always decidable.
For example, the halting problem on an empty tape is proven to be undecidable:
$$H_0 = \{w \in \{0,1\}^* \mid ...
- 55
1
vote
1
answer
84
views
Are there other types of computational problems, and specialized tools/solvers for them?
The common types of computational problems that I can find seems to be the following: decision problems, search problems, counting problems, optimization problems, and function problems.
For decision ...
- 17
0
votes
1
answer
70
views
Equivalence of Infinite Turing Machines
Given a Turing machine M, is it true that there exist infinitely many Turing machines equivalent to it?
1
vote
1
answer
86
views
Path Coloring NP-hard
Is there a simple way to show Path Coloring is NP-hard ?
Path Coloring. On input $(G,P,k)$ where $G$ is undirected graph and $P$ is a set of simple paths (no repeated vertex). Decide if each path in $...
- 225
0
votes
1
answer
81
views
Clarifying an interpretation of the definition of the subset-sum problem
I recently heard about the subset-sum problem, and its definition got me thinking.
Is it true that, to answer "yes" to a specific instance of the subset-sum problem, an explicit subset also ...
- 103
3
votes
1
answer
92
views
Construct PCP instance for given Index list
Given an index list I and an Alphabet E, i want to construct the two lists of words a and <...
- 133