# All Questions

2 views

### Arithmetic problem that is $\#P$-complete

Is there an arithmetic problem that is $\#P$ complete and decision version is in $PP$?
12 views

### Is there any problem which is in NP but not a NPC and NPH?

I just started learning Complexity theory. And I am searching from the last four five days, only one thing. Is there any problem which is in NP but not a NPC and NPH. Look in this diagram, Ther is ...
7 views

### Which crossing over technique is the best for a Parallel Machine Scheduling problem in GA?

I have a genetic algorithym to solve a machine scheduling for a job-shop problem contains $i$ jobs, $j$ machines and each jobs have $k$ processes. It is called ...
24 views

### What would faster Fourier Transform(FFT?) and/or multiplication algorithms imply?

There are many problems which have implications on P vs. NP and other complexity classes. Supposing that we're interested in Fourier transforms and/or multiplication algorithms, do faster Fourier ...
46 views

### incremental knapsack

Is there a way to compute the knapsack problem incrementally? Any approximation algorithm? I am trying to solve the problem in the following scenario. Let D be my data set which is not ordered and ...
46 views

### Number of ordinal trees with n nodes, of depth d, with l leaves

What is the number of ordinal trees with $n$ nodes, of depth $d$, with $l$ leaves? I thought that it was a known results but I could not find it, and neither did the various combinatorics whom I ...
49 views

### Max common sub forest on $k$ graphs

Not sure how to phrase this really, but here goes. Suppose you are given $k$ simple graphs, each having exactly $m$ edges. The edges in each graph are labeled from 1 to $m$. The problem is to find ...
58 views

### NP-Complete computation complexity [on hold]

Suppose X1 is NP-Complete & and X1 can be reduced to X2 in exponential time. What can we sat about the computation complexity of the problem X2? Is X2 consider NP-Hard? I know that when a problem ...
91 views

### Maximum common subgraph of two planar graphs of bounded degree k

Given two planar graphs of bounded degree (i.e. each node has no more than D edges), I'd like to find their maximum common subgraph. I know that the more general problem applied to maximal planar ...
45 views

### Set Notation in Turing Machine [on hold]

Im trying to find the set notation and grammar for the turing machine below: q0--(#/#,R)-->q1 q1--(3/3,R)-->q5(Final State) q5--(b/b,R),(3/3,R)-->q5 q1--(1/a,R)-->q2 ...
11 views

### do we need to perform both validation and verification tests to some data? [on hold]

sometimes we need to validate date and sometimes we need to verify it but programs can run normally with validation tests where there should be and verification tests where they should be, provided ...
39 views

### P subset of RP subset of NP [on hold]

I am a bit confused about $P\subseteq RP \subseteq NP$ relation. RP is class of which words can be accepted by Monte Carlo TM ($MTM$) which work like this: It always runs in polynomial time in the ...
145 views

### Standard reference for basic model theory definitions

I am trying to give a formal presentation of the model-theoretical semantics of a language and I am a bit lost in the terminology. In particular, could somebody clarify the exact definitions of ...
29 views

### ram slot graphics card a possibility [closed]

As ram is obviously so tightly tied to the processor with many more lanes than pci and especially faster than those pld ports and graphics cards often offer substantial ram beyond old hardware ...
42 views

### Combinatorial characterization of hypergraph Tseitin satisfiability

The Tseitin formulas are as follows: Given a connected graph and a function $\alpha: V \rightarrow \{0,1\}$. Associate each edge $e$ with a variable $x_e$. The Tseitin formula $G(\alpha)$ is defined ...
90 views

### NP-hardness of approximation for unconstrained submodular maximization

The problem of unconstrained submodular maximization can be phrased as follows: Given a non-negative submodular function $f$ on a domain $D$ find a set $S \subseteq D$ maximizing $f(S)$. Here a ...
36 views

### Sequential execution in π-Calculus

I am just starting into process algebra (π-Calculus) for formally defining the operational semantics of a system. One common statement that I come across that π-Calculus is used for Concurrent and ...
77 views

### Finite objects for which isomorphism is NP-hard or harder? [on hold]

Crossposted from MO where answer didn't convince me and IMHO there are contradictory comments of high reputation users. Are there finite objects for which deciding isomorphism is NP-hard or harder? ...
27 views

### Vector Product in the constrinats on an optimization problem

Can the following optimization problem be solved using Semi-Definite Programming or Linear Programming. We are given a data matrix $A$, which is known. We have the following optimization problem. This ...
46 views

### Cycle cover for structured graph

Consider the undirected graph $G=(V,E)$ example below. More precisely, the vertices in $V$ are labelled with $(x,y)$-coordinates and there is an edge between every vertices sharing the same $x$ and ...
23 views

### Reduction of 3-SAT to Vertex Cover? [closed]

Can someone explain to me in the most simplest possible way, how to reduce $3-SAT$ to $Vertex\:Cover$ ? I am following the explanation here(scroll to page 4 bottom). I understand the basic setup of ...
24 views

### Design approach for modeling human agents similar to cellular automaton and multi-agents in social systems [on hold]

I want to look at modeling human agents in a simplified form, similar to cellular automaton but include a 'network effect', as in linking the agents. Where I can include simple decision making ...
18 views

### Finding percentage of similarity between varying sets of integers [on hold]

I have a challenge that I'm willing to pay for consultation to resolve and ultimately would like to have create a working relationship with someone as a result of this post. I have an application ...
71 views

### DFA (Deterministic Finite Automaton) ending with 11 or 10 [closed]

I need to determine a DFA (Deterministic Finite Automaton) that accepts Strings of the Alphabet ε = {0,1} in which the second to last number must be 1. I came up with this NFA: It seems to be ...
53 views

### Does PEG contain CFG?

Despite their considerable expressive power, all PEGs can be parsed in linear time using a tabular or memoizing parser (8). These properties strongly suggest that CFGs and PEGs define incomparable ...
45 views

### Divide and conquer algorithm to find which value appears only once [closed]

Good evening I have a question about desgining algorithms. The question is: You are given a sorted array of numbers where every value except one appears exactly twice; the remaining value appears ...
62 views

### Counting points on curves

It is known (see "Counting curves and their projections" (free version) by von zur Gathen, Karpinski, and Shparlinski) that the problem of finding the number of $\mathbb{F}_q$-rational points on a ...
173 views

### Where is the quote “Informal proofs are algorithms, formal proofs are code” from?

Does anyone know the origin of the quote, Informal proofs are algorithms; formal proofs are code. Its made in Benjamin C. Pierce et al.'s Software Foundations.
56 views

### Trade-off between number of spheres and wasted space in covering a 3d object by spheres

Consider the following optimization problem: Input: a 3-dimensional "object" $O$. Output: a covering of $O$ by a list of $k$ spheres $S_1, \ldots, S_k$ (given by their centers and radii) minimizing ...
35 views

### How do I figure out how to combine simpler quantum gates to create the gate I want?

I want to create other quantum gates from the basic building blocks of a universal quantum gate set. I've been playing with IBM's quantum computing interface for that. I wanted to create a Toffoli ...
22 views

141 views

### Testing Isomorphism of projective planes

Miller showed that isomorphism testing of projective planes can be done in $v^{O(\log \log v)}$. I would like to know whether Babai's techniques that led to the quasipolynomial time algorithm for GI ...
130 views

### 3-color a cubic graph such that a MIS receives only two colors

According to Brooks'_theorem, a cubic graph (3-regular graph) containing no $K_4$ can be properly colored by three colors. (Such a color can actually be found in linear time, which is not our primary ...
66 views

### Differential Privacy and Randomized Responses for Counting Queries

I'm trying to understand a basic randomized response mechanism for differential privacy (concrete definition not relevant for the question), but I have some trouble understanding the last step in the ...
93 views

### Kleene closure of DFA

Given an $n$-state DFA (over a binary or any fixed alphabet), what is the complexity of computing its Kleene closure DFA? What is the largest possible/known blow-up in the number of states?
149 views

### Complexity of $r$-sum as a function of integer sizes

Given $n$ distinct integers whose absolute value is of size $c_{n,k}=\lceil n^{1/k}\rceil$ bits ($c_{n,k}$th bit position is always $1$ for absolute value) we know that using dynamic programming we ...
68 views

### Are biases necessary to make neural networks universal approximators when using sigmoid activations?

In a neural network, a bias is a constant term that is added to the weighted input in a neuron/unit: output = activation_function( input1*weight1 + ... + inputn*weightn + bias) I can see that the ...
172 views

### (Self-)citation etiquette

This is particularly pertinent to the CS culture, where competitive conferences are often the main publication unit, which are then (sometimes) followed by journal versions. Suppose that a paper was ...
86 views

### What points should I mention and how? - in a theory paper's introduction part

this is my first time writing a theory paper and I am getting carried away with thoughts when I am writing theory paper's introduction, I have read some web pages telling what points should I mention ...