0
votes
0answers
2 views

Arithmetic problem that is $\#P$-complete

Is there an arithmetic problem that is $\#P$ complete and decision version is in $PP$?
-1
votes
0answers
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 ...
-1
votes
0answers
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 ...
1
vote
0answers
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 ...
-1
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
-5
votes
0answers
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 ...
5
votes
1answer
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 ...
-2
votes
0answers
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 ...
-4
votes
0answers
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 ...
-4
votes
1answer
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 ...
6
votes
1answer
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 ...
-4
votes
0answers
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 ...
4
votes
0answers
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 ...
9
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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? ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
-5
votes
0answers
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 ...
-2
votes
0answers
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 ...
-2
votes
0answers
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 ...
-5
votes
0answers
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 ...
5
votes
0answers
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 ...
-3
votes
0answers
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 ...
1
vote
0answers
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 ...
4
votes
1answer
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.
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-3
votes
0answers
22 views

shifting of a Turing Machine with additional finite memory of size $n$ into a standard TM [closed]

The question itself: Let us define a generalization of Turing Machines to include a finite memory of >size $n$. We denote such a Turing Machine formally as: $M_{mem} = (Q, Σ, γ, ...
-2
votes
0answers
27 views

Most General of a pair of unifiers [closed]

I'm doing a past paper question for my logic programming exam, and a question that came up was regarding which unification was most general. I'm not quite sure what's the best way to go about this ...
6
votes
0answers
37 views

Framing the Count-Min Sketch as a Random Projection?

The count-min sketch data structure is used to estimate the frequencies of individual elements in a data stream. The authors note that the analysis of their data structure is simpler than other ...
-1
votes
0answers
54 views

If quantum mechanics is unitary, how can information be deleted? [on hold]

Assuming that $|\psi\rangle$ is the current state of an $n$-qubit quantum computer, unitarity of the time evolution operator in quantum mechanics means that given any earlier state $|\phi\rangle$, ...
3
votes
1answer
200 views

The maximum number of induced cycles in a simple directed graph

Is the maximum number of induced circuits in a simple directed graph known? I tried the family of graphs suggested by David and the number of induced cycles is seems to be exactly $3^{n/3} + ...
5
votes
0answers
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 ...
8
votes
1answer
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 ...
0
votes
1answer
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 ...
4
votes
1answer
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?
0
votes
1answer
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 ...
1
vote
1answer
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 ...
6
votes
1answer
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 ...
2
votes
0answers
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 ...
3
votes
0answers
60 views

Are there analogues of Specker sequences for other complexity classes?

Consider the standard definition of computable real numbers: a real number $r$ is computable just in case $r$ is the limit of a sequence $(a_i)_{i \in \mathbb{N}}$ such that (1) the function $i ...
-1
votes
0answers
47 views

Why does a Turing machine with a finite operating interval eventually halt? [on hold]

This question is originally from Boolos, et al. (2007, p. 135). The operating interval for a Turing machine's computation beginning with input n consists of the numbers 0 through n together with the ...
10
votes
1answer
224 views

How do journals serve the TCS community?

In the past, journals were the main way scientific/mathematical discoveries were disseminated and vetted. In some areas, they still are. However, in (theoretical) computer science that role is almost ...
8
votes
1answer
115 views

Label-disjoint paths in directed graphs

Checking if there are two edge-disjoint paths from $s$ to $t$ in a given undirected graph $G$ is in P via a standard solution based on maxflow. I am interested in the complexity of the following ...
2
votes
2answers
104 views

Collection of failed attempts to solve X

I've been half-jokingly entertaining the idea of trying to blog about "n ways not to solve P vs NP" in the indefinite future, and in my search came across the How not to solve P=NP? question on ...
29
votes
3answers
2k views

Turing Machine restrictions that render halting decidable

If one restricts Turing Machines to a finite tape (i.e., to use bounded space $S$), then the halting problem is decidable, essentially because after a number of steps (which can be calculated from the ...
0
votes
1answer
53 views

Semantic equivalence using a model of computation of two languages

I am relatively new to the field of language semantics. However i had a question pertaining to language equivalence (i did read about the question, however my approach is slightly different and hence ...

15 30 50 per page