Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

0
votes
0answers
11 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
24 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
53 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
44 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
28 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
19 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
11 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
7 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
34 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
20 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
50 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
23 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
103 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
13 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
129 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
30 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 ...
0
votes
1answer
49 views

What is the complement of empty language? [closed]

Consider a turing machine that accepts the empty language. What will be the complement of the language generated by the above turing machine? A) Recursive B) Recursive Enumerable C) Non recursive ...
4
votes
0answers
20 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
38 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
44 views

Complexity of nested loops [duplicate]

I'm trying to figure out the complexity of the following algorithm. ...
5
votes
0answers
144 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
47 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.
0
votes
2answers
73 views

Tracking object problem

I have to track an object. I m confused whether its a P Problem or NP Problem?. The object is a piece of paper of white color, which matches with the background color I m working in, and also the ...
1
vote
1answer
37 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
14 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
67 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?
7
votes
0answers
168 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 ...
1
vote
0answers
32 views

Using algebraic structures to solve computer science questions (xpost from math.se) [closed]

This is a cross post from here. I would like to know of some examples or references where algebraic ideas have been used in complexity theory or the like. Examples would be parallels of ...
0
votes
1answer
62 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
15 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
54 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
78 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
43 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
54 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 ...
1
vote
0answers
39 views

Deciding coprimality of integer pairs [closed]

Given $a,b$, I know that computing $GCD(a,b)$ takes $O(log_2^{1+\epsilon}(ab))$ complexity. If we just want to decide $GCD(a,b)=1\mbox{ or }\neq1$ with certainty or with certain error $\epsilon$, ...
5
votes
2answers
59 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 ...
1
vote
1answer
22 views

Kth largest subset for small K

The $K$th Largest Subset problem is often given as an example of an NP-hard problem. However, the assumption is that $K$ is unconstrained, and can be as large as $2^n$. Clearly, if $K \le 3$ the ...
1
vote
1answer
25 views

Different boolean degrees polynomially related-2?

Essentially similar question to here Different boolean degrees polynomially related? (change being error condition $\epsilon\in(0,1)$). Let $p$ be the minimum degree (of degree $d_f$) real polynomial ...
3
votes
1answer
59 views

Is a Karp-Levin reduction a Levin reduction?

My understanding is that Karp many-one reductions are more general than Levin many-one reductions, and that Levin many-one reductions must allow for the number of certificates for a problem $A$ ...
1
vote
1answer
26 views

Reductions where the number of certificates from one problem can be computed for another to varying degrees

Let $A$ and $B$ be two decision problems in $NP$. Consider three cases: (1) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having exactly the same ...
1
vote
1answer
50 views

Relations among different boolean approximations

Essentially similar question to here Different boolean degrees polynomially related? (change being error condition $\epsilon\in(0,1)$). Let $p$ be the minimum degree (of degree $d_f$) real polynomial ...
-1
votes
1answer
81 views

Pumping Lemma Proof by contradiction [duplicate]

So, hi guys! I have a language which I am trying to prove that it is not regular using the Pumping Lemma. I am pretty new into the lemma so I would appreciate any help.The language is $$L = \{w | w ...
3
votes
1answer
46 views

What is the relation between arithmetic circuits and straight line programs?

One definition of arithmetic circuits is as follows: An arithmetic circuit $\Phi$ over the field $\mathbb F$ and the set of variables $X$ usually, $X = \{x_1, \dots , x_n\}$) is a directed ...
0
votes
1answer
30 views

NP Problem and reduction [duplicate]

I've read that "Every problem in NP can be reduced to every NP-complete problem". I want to know why the term "Every" is important.If we have one problem in NP that is reduced to one NP complete ...
1
vote
1answer
42 views

Lower-bounds of a given problem

I have the following problem: You have n objects that have identical weight except for one that is a bit heavier than the others. You have a balance scale. You can place objects on each side ...
1
vote
1answer
44 views

Different boolean degrees polynomially related?

Let $f$ be a Boolean function. Let $p$ be the minimum degree real polynomial that represents $f$ with degree $d_f$. Let $p_\epsilon$ be the minimum degree real polynomial with degree ...
-1
votes
1answer
33 views

Limiting capacity of knapsack to a polynomial function of elements in the Knapsack problem

I saw somewhere that if we limit the capacity (weight) of the knapsack to a polynomial function of elements then the class of the problem changes to P, but it didn't say why. I can't figure out why is ...