Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Polynomial Time Algorithms:
TR98-031 | 4th May 1998
Dimitris Fotakis, Paul Spirakis

Graph Properties that Facilitate Travelling

In this work, we study two special cases of the metric Travelling Salesman
Problem, Graph TSP and TSP(1,2). At first, we show that dense instances of
TSP(1,2) and Graph TSP are essentially as hard to approximate as general
instances of TSP(1,2).

Next, we present an NC algorithm for TSP(1,2) that ... more >>>

TR23-200 | 6th December 2023
Joseph Shunia

An Efficient Deterministic Primality Test

Revisions: 1 , Comments: 4

A deterministic primality test with a polynomial time complexity of $\tilde{O}(\log^3(n))$ is presented. The test posits that an integer $n$ satisfying the conditions of the main theorem is prime. Combining elements of number theory and combinatorics, the proof operates on the basis of simultaneous modular congruences relating to binomial transforms ... more >>>

ISSN 1433-8092 | Imprint