Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

7
votes
1answer
97 views

What do we know about NP ∩ co-NP and its relation to NPI?

A TA dropped by today to inquire some things about NP and co-NP. We arrived at a point where I was stumped, too: what does a Venn diagram of P, NPI, NP, and co-NP look like assuming P ≠ NP (the other ...
1
vote
1answer
39 views

How can Weighted MaxSAT be in $FP^{NP}$ when dealing with large weights?

Weighted MaxSAT is in $\mathrm{FP^{NP}}$, see [1] Theorem 17.4, i.e. Weighted MaxSAT can be solved with at most a polynomial number of calls to a SAT oracle. The proof in [1] makes use of binary ...
3
votes
1answer
222 views

Example of exponential algorithm performing better than a polynomial one?

I have a weird question. I was just wondering if there were some problem with two solutions; one (A) being exponential time, the other one (B) being polynomial time. However the constants involved ...
1
vote
2answers
56 views

Complexity of 4-coloring a map with constraints

The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color. In fact, there exists a ...
0
votes
1answer
35 views

Whats is the meaning of polynomial run-time in input size ? [duplicate]

If an algorithm runs in exponential time with exponential input then we say it runs in polynomial time ? Why ? Doesn't the algorithm run in exponential time anyway ? How the input size affects ? ...
3
votes
1answer
54 views

FP^NP-complete problems

Is there any other standard FP^NP-complete problem other than the Traveling Salesman Problem? For instance, in the canonical propositional logic?
1
vote
1answer
36 views

Verifying a solution vs. finding one

There is an algorithmic problem $A(n)$, where $n$ is the size of the problem. It is known that, for every candidate solution S, the time it takes to verify whether it is a correct solution to $A(n)$ ...
2
votes
1answer
40 views

Can number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states? [closed]

As title says, can the number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states - that is if the NFA recognizes the same language as the DFA and has $n$ states, can ...
6
votes
1answer
30 views

Versions of NP with different logical unifiers

One formulation of NP is this: a language is in NP if it can be solved in polynomial time by an algorithm that has access to a special "Nondeterministic Bit" function, which branches the world into ...
1
vote
0answers
15 views

Technical clarification on BSS model

In BSS model in which one is allowed $\{+,-,\times\}$ operations, how is division and square root handled? Is there a typical procedure dealing with these involved situations?
6
votes
2answers
113 views

Can element uniqueness be solved in deterministic linear time?

Consider the following problem: Input: lists $X,Y$ of integers Goal: determine whether there exists an integer $x$ that is in both lists. Suppose both lists $X,Y$ are of size $n$. Is there a ...
0
votes
1answer
55 views

Running time of partial algorithms

What is the correct term for the maximal running time of a given algorithm on all inputs of length bounded by given $n$, on which the algorithm halts? Assume, if necessary, that the halting problem ...
1
vote
1answer
81 views

Artificial intelligence - bridge and torch problem

I am doing a artificial intelligence course as part of my computer science degree. I am stuck on a question about searching. The question is a version of the Bridge and torch problem. Five people ...
2
votes
1answer
22 views

Looking for an example of proving space upper bounds for computing functions on a DTM

Like think of the function $f\colon \{ 0,1\}^* \rightarrow \{0,1\}^*$ which maps a binary string string $x$ to say a string of $0$s of length $\vert x \vert ^2$ whre $\vert x \vert$ is the length of ...
2
votes
1answer
43 views

What is the implication of NP-completeness if P=NP?

If a certain problem $X$ is NP-complete and $P\neq NP$, then $X$ is not polynomial. But we still don't know that $P\neq NP$, so in theory $X$ may be polynomial. Does the fact that $X$ is NP-complete ...
5
votes
1answer
83 views

Combinational Logic Circuits and Theory of Computation

I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything i have learned recently in Theory of Computation. I was thinking whether combinational ...
1
vote
1answer
40 views

Complexity of Simon's Problem

In reading the Wiki article on Simon's Problem, the article states that it takes exponential time(in the classical version) to discover the secret string S that is inside the black box. Why is this ...
0
votes
1answer
65 views

Is this problem P or NP?

Given a set of whole numbers $M=\{z_0, ..., z_n\}$ Are there $z_i$ and $z_j$ with $i \neq j$ but $z_i = z_j$? Is this Problem (surely or only probably) in $P$ or in $NP$? Is it $NP-hard$?
-1
votes
1answer
57 views

All optimisation problems have equivalent decision problems

How can we prove the theorem that every optimization problem has an equivalent decision problem, and the optimisation problem is at least as hard as that decision problem? And secondly, I'm not sure ...
2
votes
0answers
40 views

What is the trick of “adding a huge number” for in the reduction from $\textsf{3-Partition}$?

Problem: To prove the $\textsf{NP-Completeness}$ of the problem of "Packing Squares (with different side length) into A Rectangle", $\textsf{3-Partition}$ is reduced to it, as shown in the following ...
1
vote
0answers
20 views

Real versus Finite field polynomials

Let $f$ be a Boolean function. Let $g$ be the minimum degree real polynomial that represents $f$ with degree $d$. Let $g_{p}$ be the minimum degree $\Bbb F_p$ polynomial that represents $f$ with ...
0
votes
0answers
19 views

$k$-query oracle Turing machine (Sipser 9.21)

Question: A $k$-query oracle Turing machine is an oracle Turing machine that is permitted to make at most $k$ queries on each input. A $k$-query oracle Turing machine $M$ with an oracle for $A$ is ...
0
votes
0answers
12 views

Solving $Isomorphism$ using $AUTOM$ in polynomial time

Let $Iso$ be the language of all $<G,H>$ such that $G$ and $H$ are isomorphic, and $AUTOM$ be the language of all $G$'s such that $G$ has a non-trivial automorphism. I'd like to show that, ...
3
votes
0answers
70 views

Relativization of NP-completeness

This is actually exercise 3.7 from "Computational Complexity: A Modern Approach". I need to prove that the NP-Completeness of 3-sat does not relativize, i.e. I need to show that that exists some ...
2
votes
2answers
21 views

$3EQ \leq _P 2EQ$

Let: $2EQ$ - The language of all binary ($\mathbb{Z}_2$) equation sets that have a solution in $\mathbb{Z}_2$, where each multiplication is of at most two $x_i,\, x_j$. Meaning a set of equations of ...
1
vote
0answers
18 views

Proving $CVal$ is $RP$-hard

Let CVal be the language of all $<C,s>$ where $s$ is an $n-$tuple of binary values ($\{0,1\}$), such that $C$ is a variable-free boolean circuit (gates $\wedge$, $\vee$, $\neg$, $0$, $1$), and ...
5
votes
2answers
61 views

Common method for solving satisfiability problems which lie in P

I know from Schaefer's Dichotomy Theorem that only a few types of satisfiability problems are in P and any other problem is NP-complete. However, all of the algorithms I know for them use specific ...
3
votes
1answer
24 views

Proving $DTime(n^3) \subset PSpace$

It is pretty obvious that $DTime(n^3) \subseteq PSpace$, since $DTime(n^3) \subseteq DSpace(n^3) \subseteq PSpace$, but I fail to see how to find such a language $L$ so that $L\in PSpace\,\,\,$ yet ...
11
votes
1answer
135 views

Why is this argument for $P\neq NP$ wrong?

I know its silly, but i managed to confuse myself and i need help settling this Suppose $P=NP$, then clearly for every oracle $A$ we have $P^A=NP^A$ which contradicts the fact that there exists some ...
1
vote
0answers
16 views

How to find (real-valued) roots of matrix polynomial

Assume you have a fixed ($d=O(1)$ for that matter) degree matrix polynomial $$P(X)=A_0+A_1\cdot X+A_2\cdot X^2+\ldots+A_dX^d$$ Where $A_0,A_1,\ldots A_d\in\mathbb N^{n\times n}$ are given as input. ...
4
votes
2answers
176 views

Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?

Let $\mathrm{LOG}_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$. Obviously, this class is a ...
2
votes
0answers
32 views

Weakest reduction for P-completeness

It is common to define $P$-completeness with respect to logspace many-one reductions. I am looking for a complexity class $C$ such that if $C=P$ then all problems in $P$ are $P$-complete under ...
4
votes
0answers
22 views

Fastest known complexity for combinatorial ILP algorithm?

I'm wondering, what is the best known algorithm, in terms of Big-$O$ notation, to solve Integer Linear Programming? I know that the problem is $NP$-complete, so I'm not expecting anything polynomial. ...
0
votes
1answer
59 views

closure property on languages

The above image, taken from planetmath.org, describes the closure property on REG (regular), DCFL (deterministic context-free), CFL (context-free), CSL (context-sensitive), RC (recursive), RE ...
1
vote
1answer
35 views

IS and matching

I have 2 different but similar problems, one belongs to NP and one to L and I don't understand why. First problem: Input: an undirected graph G with n^2 vertices. Question: Is there exist in G a ...
1
vote
2answers
46 views

Complexity of nested loops [duplicate]

I'm trying to figure out the complexity of the following algorithm. ...
5
votes
1answer
177 views

Travelling with the most efficient path

A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time. The problem is: you have to travel $1000$ km. The only gas ...
-2
votes
1answer
48 views

Proof problem is NP [closed]

Hi need help to proof: For each A,B problems , if A ≤p B , and B ∈ NP then A ∈ NP Thanks.
1
vote
1answer
48 views

Decrease space complexity, how will time complexity increase?

I have a problem whose lower bound of problem complexity is proven to be $O(n+m)$ (n < m) and I also come up with an algorithm whose time complexity is $ O(n+m)$, space complexity is $ O(n)$. (All ...
1
vote
1answer
15 views

The number of operations of Explicit and Implicit Euler for 1D hear equation

I'm studying with "Numerical Solution of Partial Differential Equations by K.W.Morton and D.F.Mayers". On page 25, it says "2(add) + 2(multiply) operations per mesh point for the explicit algorithm ...
-1
votes
2answers
70 views

What is complexity of checking whether a natural number is a perfect square? [closed]

As the title says, what is complexity of checking whether a natural number is a perfect square?
8
votes
0answers
187 views

Choosing a subset of binary variables to maximize the sum of the highest $K$

Given $N$ probabilities $P_1,\dots,P_N$ and rewards $R_1,\dots,R_N$ and the integers $M,K$ $(N>M>K)$ as input, define the random variables $X_1,\dots,X_N$ as $$X_i=\begin{cases} R_i & ...
2
votes
1answer
35 views

Definition of $D^P$?

What is the definition of the complexity class $D^P$? In recent papers I sometimes read $D^P$ but could not find a definition of it. Unfortunately Complexity Zoo does not give one, too. Is it the ...
0
votes
1answer
65 views

Example of a boolean function

Is there an example of real polynomial representation of a Boolean function with $4$ variables whose polynomial degree is $2$ that depends on $4$ variables?
0
votes
0answers
16 views

Block sensitivity and degree

$\newcommand{\bs}{\mathrm{bs}}$What is the largest gap known between block sensitivity ($\bs(f)$) of a boolean function ($f$) and degree of a polynomial ($\deg(f)$) that represents/approximates it? ...
1
vote
0answers
63 views

Is the multiset - subset sum problem variant not in NP?

If the input for a subset sum problem is a multiset (with repetitions) instead of a set (without repetitions), e.g. Set $a = ...
0
votes
3answers
84 views

Given a minimum vertex cover can we find all the others in polynomial time?

Having found one minimum vertex cover of a connected undirected graph, is there a known polynomial-time algorithm for finding all the other minimum vertex covers of the graph, or is this problem ...
2
votes
1answer
50 views

Complexity of a knapsack variant

Consider the following traditional integer knapsack problem: $\max \sum_{i=1}^k p_i \cdot x_i\\ \text{s.t.} \sum_{i=1}^k w_i \cdot x_i \leq W \\ x_i \in \{0,\ldots,k_i\} \text{ for each } i$ Now ...
1
vote
1answer
65 views

Lower bound on approximation degree in Nisan-Szegedy

In Nisan and Szegedy's 1994 paper "On the degree of boolean functions as real polynomials"[1] Lemma 3.8, how does proof work for $\widetilde{\deg(f)}\geq \sqrt{\,\tfrac16\mathrm{bs}(f)\,}$? It ...
4
votes
2answers
67 views

MAX,MAJ variants of NP complete problems

We know that MAJSAT is PP-complete. Is it generally true that given an NP-complete problem, its majority variant is PP-complete? For example, MAJ-Set-Splitting: are the majority of partitions of ...