All Questions

Filter by
Sorted by
Tagged with
-4
votes
1answer
956 views

Subset-Sum modulo small primes

I was thinking about the strategy of solving Subset-Sum (with a set of size n and integers having n bits each) by using Dynamic Programming (described here: http://en.wikipedia.org/wiki/...
-4
votes
1answer
2k views

Find sentences with similar relative meaning from a list of sentences against an example one

I want to be able to find sentences with the same meaning. I have a query sentence, and a long list of millions of other sentences. Sentences are words, or a special type of word called a symbol which ...
-4
votes
2answers
87 views

Is it possible to have a sorting algorithm that computes faster than QuickSort? [closed]

Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted. (notice how many times the 2 is touched [circled in red ...
-4
votes
1answer
440 views

Proving NP-hardness of scheduling problem (total weighted completion time)

Consider the problem $P \mid \mid \sum w_j C_j$. I want to prove that this problem is (strongly) NP-hard by reducing from $3$-Partition, but I am not really sure how to do this. Just to be precise, ...
-4
votes
1answer
205 views

What exactly is a search space? [closed]

I am new to CS so excuse my question if it seems very rudimentary. I just want to make sure I understand the terminology 100% correct as I go along. Is a "search space" the total amount of all the ...
-4
votes
1answer
159 views

How to reduce LCS from Vertex-Cover [closed]

I am trying to understand the demostration of intractability of the LCS problem, as stated as a reduction from Vertex-Cover problem, and so far, i'm stuck with the demostration of the problem in this ...
-5
votes
1answer
659 views

What is the complexity of the fastest method of k-coloring any graph? [closed]

I heard brute-force is the only method. Is there any other way? Is there a way to prove that the complexity cannot be exponential?
-5
votes
1answer
2k views

Developing A Perfect Tic-Tac-Toe Player - AI [closed]

I'm interested in AI as an area to study on in MSc. I don't have much prior knowledge. So, I decided to develop an AI that plays Tic-Tac-Toe perfectly, as an introduction. I've made some progress that ...
-5
votes
1answer
310 views

Solving a system of linear inequations

Consider the following system of inequalities: $Ax=b$; $x\geq 0$; A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. a) How feasibility of this system can ...
-5
votes
1answer
119 views

What do you think of Bokov's “CNF-SAT is in P” proof? [closed]

There are now several versions of G. V. Bokov's paper "Complexity of the CNF-satisfiability problem", cf. https://arxiv.org/abs/1804.02478 In the most recent version of his paper, the proof is only ...
-5
votes
1answer
139 views

Should GCT focus on $PSPACE\not\subseteq P/poly$?

GCT tries to show $P$ is not $NP$ by showing $NP$ is not in $P/poly$. Could it be useful in showing $\Sigma_{i+1}\not\subseteq P^{\Sigma_i}/Poly$ at every $i>0$? Suppose if it turns out that $\...
-5
votes
1answer
556 views

Is 3SAT problem APX-hard or not?

Could you point me a reference, an answer or it is an open question?
-5
votes
1answer
242 views

Does a Non deterministic TM halt after the same number of steps on the same input? [closed]

Let $M$ be a Turing Machine (TM) which decides a certain language. Enter an input $x$ to $M$ and let the machine compute on $x$. After some time, $M$ will halt. If $M$ is a deterministic TM, it will ...
-5
votes
1answer
377 views

Theoretical Computer Science or Sensor Networks

I am a first year PhD student in computer science. The major areas my supervisor is working with are: Theoretical Computer Science (knowledge representation, uncertainty, etc.) and wireless sensor ...
-5
votes
1answer
2k views

Proof that DFA that accepts string has NFA that accepts reversal of string

I have seen descriptions for an algorithm that can take a regular deterministic finite automata and create a non-deterministic finite automata that is guaranteed to generate the reverse of string ...
-5
votes
1answer
1k views

Alternative Turing Machine Proofs

I am asking this question again. I am aware of, and have read the other similar "alternative proof TM" questions, but unfortunately, they do help me. I am looking for a TM Halting Problem proof that ...
-5
votes
2answers
2k views

Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. Suppose that G is a weighted undirected graph with positive ...
-5
votes
1answer
706 views

Self-avoiding walk in Graph [closed]

Short question: How many self-avoiding-filling-polygons are there in a grid-graph of $n×n$? Long question: Edit: This question is not about p = np. I am searching for a way to calculate the numbers ...
-5
votes
1answer
289 views

whats the difference between nondeterminism and parallelism? [closed]

pondering another Q/A & the responses on here[1] leads to this question: whats the difference between nondeterminism and parallelism? am aware of basic answers. have some of my own ideas on ...
-5
votes
2answers
963 views

Proof of correctness of in-place Quick sort

I have found proof of correctness of Quick sort (not in-place version), Please refer me a proof of correctness of in-place Quick sort, or provide proof here is very appropriated. a typical ...
-5
votes
1answer
985 views

Polynomial time algorithm to solve the TSP on an m by n solid grid

Is there a polynomial algorithm to solve TSP (or Ham Cycle) on an m by n solid grid graph whose points are at unit distance apart? I've heard about Umans and Lenhart research paper but reading such ...
-5
votes
2answers
167 views

A sandwich Algorithm / Data Structure [closed]

$O(n^c)$ is asymptotically greater than $O(\log^d n) $ for all possible pair of values of $c$ and $d$. Can you give an example of a problem (or data structure) which has running time (or query/...
-5
votes
1answer
89 views

NP hard? Maximize the average for a subset of numbers

Given a set of real numbers, choose a subset to maximize the average subject to the average not exceeding a given threshold. Is it NP hard? I think so, but I cannot come out with a proof. Thanks a ...
-5
votes
1answer
126 views

Are there proofs which show that AIs are bound to be “worse” than the human brain? [closed]

I was talking with two PhDs (both teach IT related subjects) about artificial intelligence the other day. They were in agreement that an AI can never reach the level of the human brain, but failed to ...
-5
votes
1answer
144 views

Do irrational number contain infinate/every patterns of sequences? [closed]

I guess the question is "does an 'infinite' number of patterns imply 'every' number of patterns?" For instance, if you could quickly calculate the decimal sequence of π, could you not (in ...
-5
votes
2answers
1k views

Deterministic CFL closure Property Homomorphism [closed]

I tried to research the following question with no results: Can you find one example where the following holds true: Let L = {xxxxxxx} be a deterministic-context-free Language and Let h(...) = xxxxx ...
-5
votes
1answer
206 views

Does any DAG can be topologically sorted? [closed]

I am not good enough in computer science. My intention is to solve some programming problem in terms of DAG's. The key point is that before getting them into database, I need run "topological sort" in ...
-5
votes
1answer
137 views

Dance Partner Problem NP-completeness [closed]

I really can't think of a concise way to phrase this problem, which makes it hard to search for, so forgive me if this is a duplicate question. I've come across a problem and I would like to know if ...
-5
votes
1answer
104 views

non deterministic algorithm always find the right solution? [closed]

i'm confused since i see some books mention the NP time algorithms as "very lucky" that means it always finds the right path? also can someone explain the coming points to me please... A ...
-5
votes
1answer
115 views

A simple challenge

Consider the following problem: given a number $n$, an alphabet $\Sigma$, and a finite language $L$, how many strings of length $n$ in $\Sigma^*$ contain at least one word $w\in L$? E.g. ...
-5
votes
1answer
233 views

Some questions (still) unresolved about braids?

I was looking for interesting questions pertaining to braid theory. I don't know if the following are considered important, but I'd like to ask: (1) in relation with the following link, is it true ...
-5
votes
1answer
236 views

Can on every instance P = NP? [closed]

I want to ask a question concerning some aspects of the P vs. NP problem. NOTE: Possibly by "popular" standards i am a crank (i tend towards P=NP), but lets focus on the issue (please with a grain of ...
-5
votes
2answers
617 views

open problems on $NP$-complete? [closed]

How can we find the list of open problems on $NP$-comlpete?
-5
votes
1answer
307 views

Attacking TSP via small nonintersecting circuits

Consider the problem of finding smaller "non-intersecting" circuits or paths in graphs embedded in the euclidean plane (visiting all vertices) in the sense of geometric intersections of edges plotted ...
-6
votes
3answers
334 views

How can I call functions that are not “first-class functions”?

I mean, is there an antonym for "first-class function"?
-6
votes
5answers
24k views

Application of calculus in computer science

Where are derivatives and integrals used in the field of Computer Science? What are their applications?
-6
votes
1answer
347 views

What function has the signature $ A \times \left ( B + C \right ) \rightarrow \left ( A \times B \right ) + \left ( A \times C \right ) $?

$ A \times \left ( B + C \right ) $ is isomorphic to $ \left ( A \times B \right ) + \left ( A \times C \right ) $, right? That means there's a function from one to the other and another function back....
-6
votes
1answer
956 views

why is a Turing machine defined as a 5-tuple? [closed]

[Edited to provide better context.] In a comment on meta, JɛffE suggested that this would be a good topic for a question to ask here. why is a Turing machine defined as a 5-tuple?
-6
votes
1answer
206 views

Is the sub-bit model of quantum computation equivalent to other models? [closed]

In a comment to this question Peter Shor asked me for a reference about the third described in the question point of view, namely, that quantum computers can be described as computers that can ...
-6
votes
2answers
420 views

Genetic algorithms

Is it theoretically possible to reconstruct the contents of a file from its id using evolutionary computing? A file in this case can be a text, image, video or audio file. The 'id' in this case, ...
-6
votes
3answers
152 views

Fixed parameter tractability [closed]

Lets say I have an algorithm with complexity $O(n^k)$ where $n$ is the size of the input and $k$ is a parameter. Clearly this is superpolynomial; but in fixed parameter tractability we restrict $k$ to ...
-6
votes
1answer
2k views

Path of length k in graph [closed]

I was reading NP complete theory just thought. "Is there any path of length k in given graph" Is it polynomial time algorithm?
-6
votes
1answer
5k views

What is the advantage of red/black trees in comparison with unbalanced trees? [closed]

In which situations would I use a red/black tree instead of an unbalanced tree?
-6
votes
1answer
248 views

Lambda Calculus - are these two expressions equivalent? [closed]

(λa.(λb.λc.b)) and (λa.λb.λc.b) I was wondering if someone could explain, using mostly English, what that lambda-calculus expression is supposed to mean, and whether there is any difference between ...
-6
votes
1answer
349 views

Quantum complexity class vs classical complexity class [closed]

What is the relation between BQP complexity class and P and NP?
-6
votes
1answer
138 views

Is the difference of two languages in NP-complete an NP-complete too? [closed]

Given two languages $L_{1} \in NP$ and $L_{2} \in \textit{NP-complete}$ such that $L_{1} \cup L_{2} \in \textit{NP-complete}$, Is $L_{1}$ in $\textit{NP-complete}$ too?
-6
votes
1answer
2k views

Dynamic programming and Divide and conquer approach [closed]

How does Dynamic Programming differ from Divide and conquer approach for solving problems? Can anyone explain the essential idea of Dynamic Programming. Thanks for any help.
-6
votes
0answers
48 views

2 Approximation for Steiner tree

Considering the Steiner tree Problem on a complete Graph with metric distances, I am searching for a 2 approximation algorithm. Preferable with a factor better than 2.
-6
votes
1answer
198 views

AI or not an AI [closed]

What truely classifies a AI? IN science fiction they are thes super smart programs that usually try taking over the world. In the programming world i hear about AI for enemies in games or stuff along ...
-7
votes
2answers
580 views

Validity implies NP=#P? [closed]

Valid progams for NP imply every solution is a valid answer. NP not equals #P implies not all solutions are answers. Therefore, Validity implies NP=#P. NP is the problem class for ...

15 30 50 per page